A Classification View on Meta Learning Bandits
Authors: Mirco Mutti
Jeongyeol Kwon
Shie Mannor
Aviv Tamar
Venue: ICML 2025 poster (2025)
Keywords: Meta learning bandits
Multi-armed bandits
Contextual bandits
Regret minimization
Classification complexity
Primary area: theory->online_learning_and_bandits

Abstract: Contextual multi-armed bandits are a popular choice to model sequential decision-making. *E.g.*, in a healthcare application we may perform various tests to asses a patient condition (exploration) and then decide on the best treatment to give (exploitation). 
When human design strategies, they aim for the exploration to be *fast*, since the patient's health is at stake, and easy to *interpret* for a physician overseeing the process. However, common bandit algorithms are nothing like that: The regret caused by exploration scales with $\sqrt{H}$ over $H$ rounds and decision strategies are based on opaque statistical considerations. In this paper, we use an original *classification view* to meta learn interpretable and fast exploration plans for a fixed collection of bandits $\mathbb{M}$. The plan is prescribed by an interpretable *decision tree* probing decisions' payoff to classify the test bandit. The test regret of the plan in the *stochastic* and *contextual* setting scales with $O (\lambda^{-2} C_{\lambda} (\mathbb{M}) \log^2 (MH))$, being $M$ the size of $\mathbb{M}$, $\lambda$ a separation parameter over the bandits, and $C_\lambda (\mathbb{M})$ a novel *classification-coefficient* that fundamentally links meta learning bandits with classification. Through a nearly matching lower bound, we show that $C_\lambda (\mathbb{M})$ inherently captures the complexity of the setting.

A Classification View on Meta Learning Bandits
Mirco Mutti
Jeongyeol Kwon? 2
Shie Mannor 13 Aviv Tamar'
Abstract
Asthma Diagnosis Flowchart
MAB Exploration Plan
Contextual multi-armed bandits popular choice to model sequential decision-making. Egg. in a healthcare application we may perform vari- ous tests to asses a patient condition (exploration) and then decide on the best treatment to give (ex- ploitation). When humans design strategies, they aim for the exploration to be fast, since the pa- tient's health is at stake, and easy to interpret for physician oversecing the process. However, common bandit algorithms are nothing like that: The regret caused by exploration scales with vH over H rounds and decision strategies are based on opaque statistical considerations. In this paper, we use an original classification view to meta learn interpretable and fast exploration plans for a fixed collection of bandits M. The plan is prescribed by an interpretable decision tree probing decisions' payoff to classify the test bandit. The test regret of the plan in the stochastic and contextual setting scales with (A -Cxx (MI) log" H)),,, being M separation parameter over
Arethe symptome tyskal acthina?
Choose zm for N rounds. Text average reword:
nn
ittry//oom
sup c isthira diagnesk??
0.3
Forther histary and tast atterative diggran
Choosearm for rounds. Test aver reward:
Chosse arm for N rounds. Test average rewerd:
pationt alroody IcS contaiiing treatment?
yas
0.7
207
Peeform uparomattyy my PLT with reverubiiity test Ilesahs sapport authmma diagross?
Dagnoss
treateent?
Figure I: Left: An excerpt from a clinical flowchart for the medical diagnosis of Asthma (GIf, 2023). Right: Illustration of an interpretable exploration plan for MAB.
the size of MI, the bandits, and (M(M) novel classification- coefficient that fundamentally links meta learn- ing bandits with classification. Through a nearly matching lower bound, we show that (MI) in- herently captures the complexity of the setting.
arm depends also on a context, a vector of features that the agent observes before deciding which arm to pull. The main challenge in MABs is how pull arms in way that effec- tively balances information gathering (called exploration) and immediate rewards (called exploitation).
A multitude of decision decision-making problems, ranging from recommender systems (Li et al., 2010) to treatment allo- cation (Berry, 1978), pricing of goods (Rothschild, 1974), advertising (Schwartz et al., 2017), can be modelled as MAB problems. However, although the problem structure is fit- ting, typical MAB algorithms are often very different from human-designed decision plans. For example, consider the clinical diagnosis plan illustrated in Figure (left). In ma- chine learning parlance, this plan takes several exploration actions (diagnosis tests) to yield a diagnosis, which will later be treated by appropriate medical actions (exploita- tion). clear that (i) the plan is short fast diagnosis is imperative; and (ii) the plan is interpretable, and can be easily communicated both to physicians and patients. Our goal in this work is to develop framework for short and interpretable action plans in the setting of MABs.
1. Introduction
In the Multi-Armed Bandits model (MAB, Lattimore & Szepesvári, 2020), decision-maker, called the agent, faces a collection of unknown probability distributions over re- als, called arms, representing alternative decisions and their corresponding payoff ka. reward), which the agent re- peatedly takes, or pulls, to maximize the mean cumulative reward collected over time. In some settings, called contex- tual MABs (Audibert & Bubeck, 2010), the reward of
Equal contribution 'Technion Israel Institute of Technology " "University of Wisconsin- 'VVIDIA Research. Corre- spondence to: Mirco Mutti <mirco.m www.@etcccnnncl........
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
To this end, we consider the stochastic contextual MAB formulation, a model of aov-adversaria problems whose

---

A Classification View on Meta Learning Bandits
classification view of MABs by introducing a novel measure theoretical barriers are well-understood (Lai & Robbins, 1 1985; Auer al., 2002). Even when the context is fixed, the regret the agent has to pay, defined as the difference between the cumulative reward of their decisions and those of the optimal strategy, inevitably scales with vKH in the worst case, being H and K the number of pulls and arms respectively. The latter rate might not be compelling enough in settings in which the regret translates to money losses, such in pricing or advertising scenarios, or even negative impact on a patient's s health condition, like in the clinical diagnosis problem mentioned above.
of complexity, the classfication-ceeffiieer Cx (M) for X- separated set of bandits M and a space of tests IIc, which captures the hardness of the learning problem: When M is known, a simple Explicit Classify then Exploir (ECE) proce- dure, which runs a classification algorithm to classify the test task and then exploits the optimal policy of the classified task, achieves test regret of O --- (Bd) log' (MH) over H rounds. Through a sample complexity lower bound to identify the optimal policy at test time, we show that the factor X C (M) is indeed unavoidable in the worst case. In Section 4, we provide a practical implementation of ECE with decision trees a standard tool in interpretable deci- sion making (Bressan et al., 2024) - that nearly matches the regret above while yielding a fully interpretable exploration plan (like in Figure I right). The latter is robust to mis- specifications of M,, which is estimated through a tractable meta training routine. Notably, all of our results hold for the contextual setting. Section 5 provides numerical experi- ments that showcase our algorithms against UCB/TS- approaches for latent bandits (Hong et al., 2020a). Section 6 is dedicated to related works. The proofs of the theorems are in the appendix.
Faster performance is possible when prior knowledge about the class of bandits the agent faces may be available, such as from historical data or powerful simulators. For example, Thompson sampling (Thompson, 1933) allows to exploit prior distribution over the problem parameters through a layesian-inspired approach. In favorable circumstances, the latter yields an average regret rate that is at most loga- rithmic in the number of arms K (Russo & Van Roy, 2016). Another formulation, called latent bandits (Maillard & Man- nor, 2014; Hong et al., 2020a), assumes that the problem parameters are coming from finite collection of bandits. The latter allows trade a factor of VK with M in the regret, being M the number of bandits in the collection.
2. Problem setting
Here we consider meta learning version of latent bandits. We can interact with the collection of bandits to meta-train an algorithm that is then tested against one bandit in the collection, whose identity is not revealed to the algorithm. Unfortunately, any prior knowledge we can extract at meta training cannot improve the / /MH rate in the worst case, which holds even for collection of two bandits (Lattimore & Szepesvári, 2020). This changes when we assume that the bandits in the collection are meaningfully different, i.e., the reward distribution of their arms have some statistical separation (Chen et al., 2022b; Mutti & Tamar, 2024). The separation condition is relevant in practice: If two patients do not respond differently to at least one treatment, there is little point in modeling them with different bandits. Whereas this can help achieving fast rates, previous work, either with or without separation, do not yield interpretable plans.
Let us consider a finite collection of contextual bandit prob- lems MI == [DS where [M]] = ..I....,,,,.. Each bandit instance vi, which we will sometimes call a task, is linear contextual bandit (Wang et al., 2005) that maps an action k [K] and context x E X C RRd into a reward distribution v4(2r, k) = x 0ax + 7kk. where 0:s: E Rd is vector of parameters and 7/5 is a (subgaussian) random noise with zero mean and variance 0² S o². A special yet important case is when the space of contexts is a single- ton X' = {ar]. which we call non-contextual bandit, or just bandit for simplicity.
Following a typical stochastic bandit setup (Lattimore & Szepesvári, 2020), the decision maker, i.e., the agent, inter- acts with a bandit E M, which identity is not revealed to the agent. The interaction protocol goes as follows: At each step t > 0, the agent observes a context ø, E X drawn from some fixed distribution P, it selects an arm ky E [K], and it collects a reward r, ~ v2 [= kz). The agents decides the arm to pull according to policy र : X' - [K]. mapping between contexts and arms, which the agent updates given previous observations of contexts and rewards.
To design interpretable exploration plans for bandits, our main technical contribution is connecting ideas from the classification literature MAB analysis. In principle, the idea is to take advantage of separation to explicitly clas- sify the test task from data with high probability, and then exploit the optimal strategy for the classified task. This clas- sification view allows to break the common barriers for meta learning bandits, while providing an elegant and original characterization of the regret dynamics under separation.
The goal of the agent is to maximize the cumulative reward collected over a time horizon H or, cquivalently, to mini- mize the regret of pulling an arm other than the optimal one. For instance, to minimize the number of times treatment different from the optimal one is administered to a patient. Since the identity of the bandit problem (unobserved charac-
The contributions of the paper are organized as follows. In Section 2, we describe problem of meta learning bandits and the separation condition. In Section 3, we formalize the
2

---

A Classification View on Meta Learning Bandits
the collection of bandits MI is constructed, the meta learning problem is not easier than the classical stochastic bandit.
META TRAINING
Exploration plan
TEST F - M
MI
online (regret)
Theorem 2.1 (Lai & Robbins 1985). Let M a set of M 2 2 bandits and let X = {x} be a singleton. The test regret is Rega (M) 52 MH).
offline
Figure 2: The meta learning bandits problem setting.
The latter can be proved through a hard instance in which the two bandits are identical expect for a pair of arms whose mean reward differ for a small quantity depending on H. In many scenarios, those instances have limited interest, as we may model the pair of bandits with a single task, at the cost of a (bounded) sub-optimality. Similarly to previous meta learning settings (Chen et al., 2022b; Mutti & Tamar, 2024), we consider a separation assumption built on this premise.
teristic of the patient in the example) is hidden to the agent, the regret is typically computed over the worst-ease task in M.. Formally, the worst-case regret is given by
Regh (M) == sup E
Σ EE
max x, KE[K]
Osk re
(1)
is EM
where the contexts 21,... FH are sampled independently from the fixed distribution p and rt (x( k2) being l2- (x2)) the arm pulled by the agent.
For all i + E [M] and a policy class II, there exists at least one policy π E II s.t. Dn(PPT T ,T)) 2 X, where Du is the Hellinger distance and T Pr are the joint tattxt-am--ewworr distributions induced by TI in Vi, Vy-
Assumption 1.
In this paper. we consider a meta learning variation (e.g., Cella et al. 2020; Kveton et al. 2020) of the common bandit setup described above. The learning setting (Figure 2) is composed of two separate and consecutive stages, which we call meta training and test, respectively.
The separation guarantees that the bandits in the collection are meaningfully different, such assuming that different patient groups respond differently to at least one treatment.
Meta training. In the first stage, the agent can interact offline with the set of bandits M. Differently from a pure ex- ploration setup (Audibert & Bubeck, 2010), here we interact with set of bandits instead of a single one. We are not just interested in discovering an optimal policy for each bandit, but also to devise an exploration plan, which we denote as P Plan(MI) that we can transfer to the test phase to minimize the regret. Since the meta training itself happens entirely offline, no regret is incurred at this stage. In practice, this is reasonable when working with simulator or previously collected data, such as an historical record of treatments administered to patients. However, we may operate under resource constraints, so that it is important to investigate the sample and computational complexity of meta training.
We have now a formal picture of the setting we consider: Meta learning bandits under separation. Before going ahead with the investigation of the setting, we introduce additional notation for later use.
Notation. We will consider fixed context distribution P for both meta training and test stages. For random variable A and event &, we use Ep PA), as short- cuts for Seex P(x) [[A[s]de and frex (E)))((())) respectively. For any finite set S, we denote 2 the powerset of S. For any two probability distributions p. q over some measurable space X, let Dz(p,g) :=
Srex (Vo())- Va(x) 2
dr be the Hellinger distance between them. For every is E M, we denote Pak Ep|x 0ss] the mean of r ~ 11(x,)) for I ~ P. We fur- ther assume x T0x E [0.1] and both ||=]| |0sall to be bounded. We denote as the space of policies and the optimal policy ((()) == arg max x' (s=(m)- playing the arm KC E arg max x 0uk with the optimal mean reward for any x E X. For a bandit v; E M and policy π E II, we denote IPT the joint distribution of context- arm rewards.rds. The action gap of bandit va and context is denoted (, == x Osk- x Ou and we define A == (MEx k))
Test. In the second stage, the agent faces single and unknown bandit task v4 E M, which we call the test task, with the goal of minimizing the regret (I). This matches the stochastic handit setting exactly, except that the learning algorithm takes decisions according to the exploration plan devised during meta training, i.e., hi ~ P Plan(M) (M.). Whereas the plan fixed a priori, it is still adaptive, as it conditions the decisions with the history of interactions in the test task. For instance, the plan can be strategy to administer treatments to a patient informed by historical data.
What are the theoretical barriers for the described problem of meta learning bandits? A natural question is whether the meta training can benefit the test regret in a substantial way. Perhaps unsurprisingly, without any assumption on how 'The result is obvious from classical minimax lower bound
constructions for stochastic bandits. See the one in Chapter 15 of Lattimore & Szepesvári (2020) for gentle introduction.
NNte that, whenever the context vector is the zero vector, the gap A, collapses zero for every i. We assume that the space of contexts X' is designed properly, so that it does note include such dummy context vectors.
3

---

A Classification View on Meta Learning Bandits
3. Meta learning bandits with classification
Algorithm Explicit Classify then Exploit
1: input set of tasks M. Net
In this section, we present a framework to study meta learn- ing bandits under separation through the lenses of multi- class classification. First, we analyze the regret of strategy,
2: Initialize So =
while [Sc] [M]] =
Explicit Classify
3:
do
4:
Wt max, min.gs, (()x
Le., an exploration plan P (MI), based classifying the test task to then exploit the optimal policy of the classified task. Then, we show that classifying the test is necessary for regret minimization under separation. As we shall see, the two results are brought together by a novel measure of complexity, which we call the coaiificaatioccooffffiie
5:
Dr Neta i..d. samples drawn with T
6:
Se with Algorithm 2
7:
f 1-111
8:
end while
9: Extract the classified task m² E St and execute x (a) =
arg max Pm-
Pm- (2, k) for the remaining steps Exploit
For the ease of presentation, we assume know the true distributions of all bandits E MI, and we leave the study of misspecifications to later sections. We consider classifi- cation algorithms in the following interaction protocol:
A Algorithm 2 Update Remaining Hypotheses
input set tasks St, test ne, samples D. 2: Let é, = E ((.)) log(P,,' (2,r)) for a S.
3: Let m = arg maxies, &
4: return Si+1 + {i E S.Ie 2 Em - 3log(M/8))
1. Start with t = 0 and an initial hypothesis class S. (1,2,... M).
2. Terminate if [S&]] tion test N. ITe (either deterministically randomly) from the set of tests IIc, and draw Net- = Ō(x-() sam- ples with ne.
Otherwise, decide on a classifica-
Clearly, the smaller the hypothesis we can rule out in a single round, the easier it is to classify the test task. In the following result, we formally link the complexity of classification with the regret.
the more
3. Update the hypothesis class S with the generated samples. t + + 1 and go to Step 2.
To this end, consider simple algorithm, called Explicit Classify then Exploit (ECE, Algorithm 1), which is based on the classification protocol described above to classify the test task (lines 2-8), then deploying the optimal policy for the classified task (line 9). We can prove the following.
The complexity of classification depends on how many hy- potheses we can rule out from test n. from the remaining hypotheses each round. As we allowed to use Ō(x-²) samples, we can at least rule out A-separated hypotheses from the underlying instance. Specifically, given the remain- ing hypothesis class S₁ E 2[M] and the underlying instance i, we can remove ST., (i) == {m E (IP,, PT)) Z }} through hypothesis testing (e.g., using likelihood ratio test).
Theorem 3.1. Suppose Assumption holds with test class He and a family of M bandit instances M. Then with probability at least 1 - 6, the while-loop in Algorithm I ends after rounds with New samples per round where
To formalize the concept, we define the deterministic dlasiffcation-coefffieee
T O (Cx (Ule) log(M/0),
Nos = O (log(M/6)/X)
(4)
|S|
(x
max min max Se21MI rllle VES
(2)
Consequently, the expected test regret of Algorithm I. for H steps is
and the randomized classification-coeffiiii
Ö (= max min max SE2i PE RES E. E.-pp
S
(3)
Reg (M) S [Ca log (M/8)) + SH.
[S)
X2
In essence, these coefficients measure the classification com- plexity of class of bandits through the pessimistic rounds of classification, where S is the worst-case remaining hy- potheses when the test task is i. and IT, p are the optimal deterministic and randomized greedy strategies, respectively. The latter take the test (resp. distribution over tests) inducing the most even split (resp. expected split) of the remaining hypotheses S. Interestingly, we can derive an upper bound on the size of the split when employing the deterministic greedy strategy
The theorem states that we can identify the test task w.h.p. taking No O(x-2. Cx Cx(ee) log)(M/8) samples. We can translate the latter into regret rate by bounding the regret caused by classification failure with öH. We can set 8 = (1/H) to make the classification failure negligible, settling the regret O(^-²C, (ITc) log" (M)). Next, we show that the latter rate nearly optimal by developing a lower bound to the regret for bandits under separation.
Foor randomized classification, we can change Algorithm to perform a randomized test, and the same conclusion holds with replacing Cs by Cx-
| [
1 Cx(1e))
E
S
1
4

---

A Classification View on Meta Learning Bandits
3.1. Necessity of classification with separation
we recall a PAC-variant of DEC from (Chen al., 2022a).
Specifically, given some y >
O, we define the coefficient
While the ECE approach may not always be the best al- gorithm to minimize regret, it is near-optimal solution whenever the optimal actions and the separating actions do not overlap. To see this, suppose a family of M multi-armed bandit instances M with arbitrarily many K arms. Each gt instance has its unique optimal arm k,, but only with margin Oee), i.e., instances are not well-separated with respect to optimal arms, In such scenarios, it always better to first identify the task with X-separating arms.
dec, (M) == max WEA( M) + (EA( (E[M]
min max
ER ( - 7 R- - -- (D (us Mm (k))) (6)
where A, == 14 (kg) (k))). We can verify the follow-
ing relation between Y and decy:
Lemma 3.2. There exists an absolute constant C, > 0 such
that for all S CCM)) we have dec, (M) > 3c.
To formalize the fundamental link between regret and clas- sification, for the remainder of the section we are going to consider a class of worst-case multi-armed bandit instances MI, which we refer as hard, defined as follows:
As a corollary of (Chen et al., 2022a, Theorem 10), this implies the lower bound on the high probability regret: Theorem 3.3. There exists an absolute constant >> 0, such that if 1/H < cc, then any algorithm must suffer regret A(min(eH, C,X-HH,.2222 ((M2((()) with probability at least H/H.
1. For each bandit instance E [M]] there is a unique optimal arm k E [K] such that
Thus, any algorithm guarantees with probability at least 1- 1/H must suffer at least ((C(M))) test regret, cap- turing the fundamental limits separated bandits. Note that the lower bound depends on the randomized classification- coefficient, though deterministic strategies can still be pre- ferred due to their simplicity in practice.
3 + 10c, Mg (k,)) = Vj H
3
Ms (k)) = 4
4'
2. All other arms k [K]/ he([ are information- revealing, i.e., either one of the following holds:
(k) = 1 X
= 1 X
or (k)
2 Vi [M].
2
4. A more practical ECE algorithm
where e, A satisfy 1>> X2 > eXE - ((M)) for some suffi- ciently large absolute constant Cx > and the random- ized classification-coeffiiii
In the previous section, we analyzed the ECE algorithm in an ideal setting in which the reward distributions of all the bandits in M and the context distribution P are fully known. 5 Here, we present more practical variation of the algorithm, Decision Tree ECE (DT-ECE), which (i) is robust to misspecifications of M caused by estimation errors at meta training, (ii) only accesses samples coming from the context distribution P. (iii) lays down a fully interpretable exploration plan through a decision tree classifier.
C(M) (defined below).
Classification complexity. Let (M)) be the optimal depth of a deterministic decision tree classifier for the hard in- stance, constructed by probing the true means of separat- ing arms A == [K] {k: hE[M] Let (M) be the opti- mal average depth of randomized decision trees. In this case, the wetffiaattioncofffciieeeee in (2) can be defined as C(M) C2 (Ax), and similarly for the randomized classffiation-ccofffiieen C(M)- == (Ax)). Note that the defined previously are concerned with the (worst-case) most even split on the hypotheses St, and thus they can be interpreted as measures for greedy classification strategies. The following is a well-known re- lationship between these greedy measures and the optimal depth of (deterministic) decision trees (Arkin et al., 1993)
In this section, we work under a special case of the sepa- ration condition (Ass. 1) which assumes separation on the mean of the rewards instead of their distribution.
classificationncoeffic
Assumption 2. For some À >> O and every Vi, Vj E M,, there exists k E [K] such that Ez~plx' T (0:x - 0,x) )1 > X.
First, we describe the meta training stage with the corre- sponding estimation guarantees, sample and computational complexity (Section 4.1). Then, we present the DT-ECE test algorithm and we analyze its regret (Section 4.2).
Č(M)) I ((M) S C (Ml) & C(M) log( (M). (5)
We note that these classification complexities can be as large as M in the worst case, while in practical scenarios we can often design effective information-revealin actions to ensure C* (M) = (log M).
4.1. Meta training
In this section, we describe provably efficient algorithm to meta train an exploration plan P1 (MM) by only accessing offline simulators of the tasks in MI and samples from P.6
Statistical barriers of separated bandits. What is the lower bound to the test regret for M? To quantify this,
Algorithm 2 access P to compute the log likelihood at step 2. An analogous algorithm accessing pre-logged historical data can be developed. The reported guarantees shall transfer verbatim
FFrm here on, we denote classifcation-ccofffe as Cx (M) when the space of tests The is a (sub)set of arms.
Cx (Tc)
5

---

A Classification View on Meta Learning Bandits
Algorithm 3 Meta Training
Algorithm 4 Decision Tree
1: input simulators M,, Nest
1: input set of tasks S
2: Initialize MI =
2:
if [S] > then
3: for E [M] do
3: Compute (Mi b) + greody(S) with Algorithm
4: for k E [K] do
4:
Define t ree (5) ;= (Iu S b)
5: Sample Nest contexts X (#n P)
5:
Compute St = [vi E S His S b+ X/2)
6: Sample Nes rewards r = (Tn ~ Us (Jrn k))
6:
Compute S = {u E S pik > b X/2]
7: Compute 6.A-
(XX Xr
7:
Define t ree (S, trie)
S and tree false) S
8: Compute iusk Nest 2n I'
8:
Call Algorithm 4 on St and S recursively
9:
end if
9: end for
10: Mlpppedd(() = ([O,, [0.K, psk())
11: end for
tree(S)
12: Build decision tree classifier t eeeMM) (M) with Algorithm 4
S
((k) &
tree fulse)
13:
output exploration plan P (ban(bl) prescribed by (re)
b+2/2
S
The meta training algorithm, whose pseudocode is in Al- gorithm 3, has two main procedures. First, it estimates the parameters of each task v; by doing regression on the class of linear functions of the context (lines 1)) Second, it takes the (possibly misspecified) resulting class M build deterministic decision tree classification model over the tasks (line 12). The following lemma provides estimation guarantee over M from the analysis of random design linear regression (Hsu et al., 2011).
b-2/2
s
tree true)
Figure 3: Visualization of a generic split of tree
The meta training algorithm that we just described is fully tractable, both in terms of computational resources and sample complexity, as proved by the result below.
Lemma 4.1. Let M1 be a set of M linear contextual bandits and let M. their estimation obtained by Algorithm 3 with
Theorem 4.2. Algorithmm 3 runs in time O(d'M*//X) and collects a total number of samples
160 d log( (H)
N est
160 MKdlog(4TMMMM min(A2, X2)
min(A 2²)
For every bandit& i E [M] and arm k E [K], it holds
Finally, we can provide guarantee on the cost of the greedy approximation with respect to the depth of the optimal de- terministic decision tree on M. i.e., (M
Ep |x 0sk
x 0sal > min
A A
1 2HHK
4
Lemma 4.3. Algorithm 4 builds decision tree with depth D = Ollg M + ()x((M))
The latter guarantees that the identity of the optimal arm and the separation condition is preserved w.h.p. by the esti- mation process. As we shall see, these properties will prove useful at test stage. Before going to that, it is worth detailing how the decision tree classifier is built (Algorithm 4).
4.2. Test
Here we analyze the test algorithm implementing the explo- ration plan P Plan(M) prescribed by the decision tree classi- fier t tee (re) which call DT-ECE. As said above, this test algorithm is slight variation of ECE (Algorithm 1) and mostly follow similar steps. Here we comment on the dif- ferences and we leave a complete pseudocode to Apx. C.2.
We consider set of tests Il equal to the set of arms [K], for which we are going to test the mean reward jú against a threshold b E [0, 1]. Since computing the optimal test is NP-hard in general (Hyafil & Rivest, 1976), we turn to a greedy approximation which gives the test with the most even split (Arkin al., 1993; Nowak, 2011). Algorithm 5 in Apx. C.I gives a tractable procedure with which the greedy test can be computed. In order make the tests along the tree statistically robust when computed with samples from the test task, we consider soft splits (Olaru & Wehenkel, 2003): We let the test jix < b be simultaneously true and false inside a band around (see Figure 3).
Without turning to the appendix, we can look at the pseu- docode in Algorithm and picture that, at line 4, DT-ECE would extract a test μag < from tree(S;) on the current hypotheses S,, collecting data like in line 5 with the policy T. k prescribed by the test. Then, instead of updating the remaining hypotheses S with log likelihood tests (line 6), it takes S.+1 by following the left or right split in the tree according to whether the test resulted true or false, respectively. Those changes lead to the following regret.
under natural conditions on the size and quality of the dataset.
6

---

A Classification View on Meta Learning Bandits
Theorem 4.4. Suppose Assumption 2 holds on a set of tasks M and let (ree((M) be obtained from Algorithm 3. The expected test regret of DT-ECE (Algorithm 6) for H steps is
by mUCB and mTS is hardly interpretable nor predictable, making them and DT-FCEE orthogonal solutions for different applications rather than direct challengers. It is satisfying, however, to see that DT-ECE performance is on par with such renowned algorithms.
Rega (M) = 0 (CX(M)) log') (CX (C)MM)
A
In Figure 4 (a. b) we see that DT-ECE achieves a small regret by classifying the test task in handful of interactions (coarsely, the classification occurs at the elbow of the curves) both when separation is large (a) or small (b). DT-ECE is able to commit to the optimal strategy even before mTS, whose posterior takes slightly longer to converge around the test task, although DT-ECE suffers larger regret due to pure exploration. The most important trait of the hard instance is that optimal actions and informative actions do not over- lap, so that optimistic strategy like mUCB are bound to fail. By mostly pulling nearly optimal yet non-informative ac- tions, mUCB cannot identify the test task efficiently, and the regret grows steady. Optimism works considerably better in the rand family (Figure 4 c, d), although mUCB does not match the efficiency of DT-ECE and mTS in those experi- ments either. It is remarkable that DT-ECE can classify the test task into a set of 40, with 40 arms each, by taking less than 1000 samples on average (d).
The result above shows that DT-ECE matches the regret of ECE with factor (M) in place of the classification- coefficient Cx (M). This implies an additional log(M) fac- tor at most (see 5). This means the estimation error does not significantly affect the regret, thanks to the guarantee in Lemma 4.1. Finally, the regret holds in a contextual bandit setting, but does not depend on the size of the context d, which only impacts the meta training complexity.
5. Experiments
In this section, we provide a brief numerical validation to illustrate how the above theoretical analysis on the classifica- tion view of meta learning bandits translates to compelling empirical results, which we compare with previous methods in the literature of latent bandits (Hong et al., 2020a).7
To the purpose of the experiments, we consider non- contextual stochastic MAB setting in which the collection of bandits is fully known, without covering class misspecifi- cations. We design two family of collections, one inspired by the hard instance presented in Section 3.1, which we henceforth call hard, and one randomly generated collec- tion, which we call rand. For the former, we consider two instances with size M- = 5 and arms K" = 10, with varying values of the separation parameters X (0.4 and 0.04 respectively). For the latter, we consider a small instance M 10, K = 20 and a large instance M = 40, K = 40. We use rejection sampling to control A (set to 0.4) in the ran- domly generated collection. In all the considered instances, the reward distributions are Bernoulli.
Finally, DT-ECE comes with sharp theoretical guarantees and it is designed for the worst case, which can limit the performance of the algorithm in more forgiving instances (such as the r rand family). However, the design of a fully practical version of the ECE ideas is beyond the scope of this paper and constitute interesting matter for future studies.
6. Related work
To the best of our knowledge, our classification view of meta learning bandits under separation is original and has not been studied. There are anyway several connections be- tween our results and the literature, which we revise below.
Contextual bandits. Obviously, our setting relates con- textual bandits (Wang et al., 2005; Li et al., 2010; Abbasi- Yadkori et al., 2011; Hao et al., 2020) and, indeed, our results hold for the contextual setting. The contextual nature of individual tasks is an orthogonal dimension w.r.t. a sec- ond, unobserved context typical of meta learning settings: The task description itself.
We compare the regret suffered by our decision tree imple- mentation of the Explicil Classify then Exploit routine (DT- ECE, described in Section 4 and Algorithm 6 of Apx. C.2) with traditional bandit approaches, i.e., mUCB (Azar et al., 2013) and mTS (Hong et al., 2020a). The latter algorithms adapt UCB and Thompson sampling to the meta/latent ban- dits setting. While they are not designed to take advantage of separation specifically, they exploit knowledge of the collection of bandits and they constitute relatively strong baselines. Before going ahead with the experimental results, is worth spending a few words on how the spirit of our algorithm differs to theirs. DT-ECE is designed to produce easy-to-interpret exploration plans, which can be entirely pre-computed offline. Instead, the exploration prescribed
Latent bandits. The setting that most closely relates to ours is latent bandits (Azar et al., 2013; Maillard & Mannor, 2014; Zhou & Brunskill, 2016; Hong et al., 2020a;b; Pal et al., 2023). Actually, our setting can be seen as a partic- ular instance of latent bandits under separation and a meta learning protocol. Azar et al. (2013); Maillard & Mannor (2014) also consider bandit tasks coming from a finite and known set, with or without misspecification. They do not consider separation, which allows to specialize the regret
"The code to reproduce the experiments can be found at https://// /tte:://gtttie thub. wwwmmmttinnnmnmccceeeeeeeeeesost mi ece.
7

---

A Classification View on Meta Learning Bandits
DT-ECE
mUCB
mTS
800
150
400
regret
regret
regret
100
20
60
200
2,000
4,000
2,000
4,000
0
2,000
4,000
2,000
4,000
borizon
horizon
borizon
horizon
(a) Hardd55110 x == 0.4
(b) hard-5-10 x = 0.04
(c) rand-10-20 X == 0.4
(d) randaadd-a 40 À 0.4
Figure 4: Regret of DT-ECE (ours), mUCB (Azar al., 2013), mTS (Hong al., 2020a). Captions report envname-M-K, denoting the name of the collection of bandits, the size of the collection, and the number of arms, respectively, together with the value of the separation parameter X. The curves average 20 independent runs, shaded regions are 95% c.i.
from H))H) to Ollo H). Similarly to ours, the setting in (Zhou& & Brunskill, 2016) includes a phase in which the models are learned from data and then exploited on future tasks. In their formulation, however, the tasks are coming into a sequence online, so that the meta learning itself adds to the regret instead of being carried out offline. An offline learning phase is considered by Hong et al. (2020a) in a problem formulation that almost perfectly matches ours, yet leads to mostly orthogonal results: They do not consider separation; Their analysis is not instance-dependent and does not tie the regret to the classification complexity of the instance; They consider traditional UCB/TS-style al- gorithms in place of our ECE; They do not detail the meta training algorithm. Most importantly, our classification view is original in the latent bandits literature and constitutes the main novelty of our work.
from Thompson sampling (Simchowitz et al., 2021).
Meta learning bandits. Meta learning bandits has been considered in (Kveton et al., 2021; Hong et al., 2022b;a) where tasks are assumed come from an unknown prior. The agent aims to infer the prior from interaction, assuming it is itself coming from a known hyper-prior. This can be seen as Bayesian version of our setting, where the hyper- prior stands for the set of tasks, and the priors play the role of the tasks. Related to this stream, other works (Cella et al., 2020; Basu et al., 2021) have considered meta learning a prior over tasks for regret minimization.
7. Conclusion
In this paper, we took an original classification view on the problem of meta learning bandits under separation. Thanks to this novel approach, our work delivers on its promise of providing principled algorithms for learning interpretable and efficient exploration plans from offline data, just like they were designed by humans. As a by product to this effort, we contribute an elegant frumework to study the regret of learning algorithms through the complexity of classifying the task online within a set of previously seen tasks.
Low-rank bandits. Low-rank bandits (Kveton et al., 2017: Lale et al., 2019; Lu et al., 2021) essentially generalize the latent bandits formulation (and ours) by assuming the existence of low-rank latent representation conditioning the arms payoffs. Just like in latent bandits, previous works do not touch on the connection between classification and regret, which may be generalized to low-rank bandits.
Structured bandits. In structured bandits (Lattimore & Munos, 2014: Combes al., 2017: Tirinzoni et al., 2020) the rewards of the arms are correlated according a known structure class with hidden parameters. These parameters have some similarity of the hidden task context of our setting (and latent bandits). Our results connecting classification and regret may be generalized to structured bandits.
We believe the significance of our findings are hardly lim- ited to the considered contextual multi- aarid bandits, and that they may inspire future works targeting yet more gen- eral problem settings (and corresponding applications) by following our blueprint for meta learning with classification.
A natural next step is to introduce dynamics over contexts to extend the framework to full-fledged Markov Decision Processes (MDPs) and reinforcement learning, where we would consider a test MDP coming from a collection of MDPs, known a priori or accessed offline. A framework of similar kind has been introduced under the name of contex- tual MDPs (Hallak et al., 2015) and latent MDPs (Kwon et al., b021 2023b;a; 2024). Previous works have also studied meta learning policies for efficient exploration in MDPs and their regret (Chen et al., 2022b; Ye et al., 2023; Mutti & Tamar, 2024). None of the above has considered
Thompson sampling. Extensive work has been done over exploiting prior knowledge in bandits through Bayesian ap- proaches. The most notable is Thompson sampling (Thomp- son, 1933; Kaufmann et al., 2012; Agrawal & Goyal. 2012; Russo & Van Roy, 2016), in which knowledge over the test task is incorporated into a prior. The set of tasks of our setting can be seen as a prior, although our results are a frequentist setting. As such, they are independent from the prior distribution and robust to misspecifications, differently
8

---

A Classification View Meta Learning Bandits
classification view of the problem get efficient and interpretable exploration plans. In the MDP setting, our decision tree classifier resembles a hierarchical strategy de- ploying policies, options (Sutton et al., 1999), to probe information-reeealing states of the environment. Can these policies be learned with tractable offline algorithm? Would exploration plan enjoy similar regret guarantees beyond the contextual MAB setting? This is an exciting direction with the potential open the door to countless applications, such autonomous driving, robotics, and many others.
In Advances in Neural Information Processing Systems, 2013.
Basu, S., Kveton, B., Zaheer, M., and Szepesvári, C. No regrets for learning the prior in bandits. In Advances in Neural Information Processing Systems, 2021.
Benry, D. A. Modified two-armed bandit strategies for tain clinical trials. Journal of the American Statistical Association, 73(362):339 333-335, 1978.
Bressan, M., Cesa-Bianchi, N., Esposito, E., Mansour, Y., Moran, S., and Thiessen, M. A theory of interpretable approximations. arXiv preprint arXiv:2406. 10529, 2024.
Acknowledgements
This research was partly funded by the European Union (ERC, Bayes-RI. 101041250). Views and opinions ex- pressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them.
Cella, L., Lazaric, A., and Pontil, M. Meta-learning with stochastic linear bandits. In International Conference on Machine Learning. 2020.
Chen, F., Mei, S., and Bai, Y. Unified algorithms for with decision-estimatto coefficients: No-regret, pac, and reward-free learning, arXiv preprint 17Xiv:2209.11445, 2022a.
Impact statement
Chen, X., Hu, J., Jin, Li, and Wang, L. Understand- ing domain randomization for sim-to-real transfer. In International Conference Learning Representations, 2022b.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Combes, R., Magureanu, S., and Proutiere, A. Minimal exploration in structured stochastic bandits. In Advances Neural Information P Processing Systems, 2017.
References
Abbasi-Yadee Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
Foster, D. J., Kakade, S. M.. Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing, arXiv preprint arXiv:21 13487, 2021.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. FLAMBE: Structural complexity and representation learning of low rank MDPs. Advances in Neural Infor- mation Processing Systems, 2020.
Glf, A. Global strategy for asthma management and preven- tion. Global Initiative for Asthma, 2023. URL https: //gi nasthma org http:///ooooot/toooooo//o///
2023 /07 /GINA 2000--2223---000 -uu22-Fuull- report-eorttt 23_07_ 06 WMS .df.
Agrawal, S. and Goyal, N. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference Learning Theory, 2012.
Hallak, A., Di Castro, D., and Mannor, S. Con- textual markov decision processes. arXiv preprint 2015.
Arkin, E. M., Meijer, H., Mitchell, J. S., Rappaport, D., and Skiena, S. S. Decision trees for geometric models. In Annual Symposium on Computational Geometry, 1993.
Hao, B., Lattimore, T. and Szepesvari, C. Adaptive ex- ploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, 2020.
Audibert, J.-Y. and Bubeck, S. Best arm identification in multi-armed bandits. In Conference on Learning Theory, 2010.
Hong. J., Kveton, B., Zaheer, M.. Chow, Y., Ahmed, A.. and Boutilier, C. Latent bandits revisited. In Advances in Neural Information Processing Systems, 2020a.
Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 2002.
Hong. J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A., Ghavamzadeh, M., and Boutilier, C. Non-stationary latent bandits. arXiv preprint arXiv:2012 (0t::2//2.0::00 2,00386, 2020b.
Azar, M. G., Lazaric, A., and Brunskill, E. Sequential transfer in multi-armen bandit with finite set of models.

---

A Classification View Meta Learning Bandits
Hong, J., Kveton, B., Katariya, S., Zaheer, M., and Ghavamzadeh, M. Deep hierarchy in bandits. In In- ternational Conference on Machine Learning, 2022a.
Lale, S., Azizzadenesheli, K., Anandkumar, A., and Has- sibi, B. Stochastic linear bandits with hidden low rank structure. arXiv preprint 19X1:19010004900 2019.
Hong, J., Kveton, B., Zaheer, M., and Ghavamzadeh, M. Hi- erarchical bayesian bandits. International Conference on Artificial Intelligence and Statistics, 2022b.
Lattimore, T. and Munos, R. Bounded regret for finite- armed structured bandits. In Advances in Neural Infor- mation Processing Systems, 2014.
Hsu, D., Kakade, S. M., and Zhang. T. An analysis of random design linear regression. arXiv preprint arXiv:1/06.2366 2011.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Li, L., Chu, W. Langford, J., and Schapire, R. E. A contextual bandit approach to personalized news article recommendationn In International Conference World Wide Web, 2010.
Hyafil, L. and Rivest, R. Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1):15-17, 1976.
Kaufmann, E., Korda, N., and Munos, R. Thompson sam- pling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory, 2012.
Liu, Q., Chung, A., Szepesvári, C., and Jin, C. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, pp. 1175-5220. PMLR, 2022.
Kveton, B., Szepesvári, C., Rao, A., Wen, Z., Abbasi- Yadkori, Y., and Muthukrishnan, S. Stochastic low-rank 2017.
bandits. arXiv preprint arXiv:
Lu, Y., Meisami, A., and Tewari, A. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, 2021.
Kveton, B., Mladenov, M., Hsu, C.-W., Zaheer, M., Szepes- vari, C., and Boutilier, C. Meta-leamiig bandit policies by gradient ascent. arXiv preprint Mxiv:2006.05099 2020.
Maillard, O.-A. and Mannor, S. Latent bandits. In Interna-
tional Conference on Machine Learning, 2014.
Kveton, B., Konobeev, M., Zaheer, M., Hsu, C.ww,, Mlade- nov, M., Boutilier, C., and Szepesvari, C. Meta- thtta-hhomponn sampling. In International Conference on Machine Learn- ing, 2021.
Mutti, M. and Tamar, A. Test-time regret minimization in meta reinforcement learning. In International Conference on Machine Learming, 2024.
Nowak, R. D. The geometry of generalized binary search. IEEE Transactions on Information Theory, 57(1))77893 7906, 2011.
Kwon, J., Efroni, Y., Caramanis, C., and Mannor, S. Rein- forcement learning in reward-mixing mdps. In Advances in Neural Information Processing Systems, 2021a.
Olaru, C. and Wehenkel, L. A complete fuzzy decision tree technique. Fuzzy Sets and Systems, 138(2):221-255) 2003.
Kwon, J., Efroni, Y., Caramanis, C., and Mannor, RI for latent mdps: Regret guarantees and lower bound. In Advances in Neural Information Processing Systems, 2021b.
Pal, S., Suggala, A. S., Shanmugam, K., and Jain, P. Optimal algorithms for latent bandits with cluster structure. In International Conference on Artificial Intelligence and Statistics, 2023.
Kwon, J., Efroni, Y., Caramanis, C., and Mannor, S. Reward- mixing mdps with few latent contexts are learnable. In International Conference on Machine Learning, 2023a.
Rothschild, M. A two-armed bandit theory of market pricing. Journal of Economic Theory, 9(2):185-22, 1974.
Kwon, J., Efroni, Y., Mannor, S., and Caramanis, C. Prospective side information for latent mdps. arXiv preprint arXiv:2310.075900 2023b.
Russo, D. and Van Roy, B. An innormmtiionthhoorce analy- sis of thompson sampling. Journal of Machine Learning Research, 17(68):1-30, 2016.
Kwon, J., Mannor, S., Caramanis, C., and Efroni, Y. RI in latent mdps is tractable: Online guarantees via off-po evaluation. arXiv preprint arXiv:2406.01388 2024.
Schwartz, E. M., Bradlow, E. T., and Fader, P. S. Cus- tomer acquisition via display advertising using multi- armed bandit experiments. Marketing Science, 36(4): 500-522, 2017.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances Applied Mathematics, 6(1): 4-22, 1985.
10

---

A Classification View Meta Learning Bandits
Simchowitz, M., Tosh, C., Krishnamurthy, A., Hsu, D. Lykouris, T., Dudik, M., and Schapire, R. E. Bayesian decision-making under misspecified priors with applica- tions to meta-learning. In Advances in Neural Information Processing Systems, 2021.
Sutton, R. S., Precup, D., and Singh, S. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2): 181-211, 1999.
Thompson, W. R. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Tirinzoni, A., Lazaric, A., and Restelli, M. A novel confidence-based algorithm for structured bandits. In International Conference Artificial Intelligence and Statistics, 2020.
Wang, C.-C., Kulkarni, R., and Poor, H. V. Bandit prob- lems with side observations. IEEE Transactions on Auto- matic Control, 50(3):338-33)3 355, 2005.
Ye, H., Chen, X., Wang, L., and Du, S. On the power of pre-training for generalization in RL: Provable benefits and hardness. In International Conference on Machine Learning, 2023.
Zhou, L. and Brunskill, E. Latent contextual bandits and their application to personalized recommendations for new users. In International Joint Conference Artificial Intelligence, 2016

---

A Classification View Meta Learning Bandits
A. Auxiliary Lemmas
The following lemma is the famous Ville's inequality for super-martingales:
Lemma A.1 (Ville's Inequality). Let {Wi be a non-negative super-martingale sequence, such that
[[W2+1|Wi) S Wt,
for any 5 > O, the following holds:
P (Vi, W. < Wo/0) 2 1
The following lemmas are the standard concentration of log-likelihood values of the models within the confidence set.
The proof' are standard in model-based RL and can also be found (e.g,, Liu et al. 2022; Agarwal et al. 2020). We let D be the observational data o (z,k, k.r collected by running π on some underlying distribution v E M. We denote = (8)) Then, the following holds:
Lemma A.2 (Uniform Bound the Likelihood Ratios). With probability 8 for any > for any M,
Σ (Pg((P(()) B s log(IP (o)).
Lemma A.3 (Concentration of Maximum Likelihood Estimators). With probability 1 - 8, for all E MI, we have
1
P. (0) (o)
D (P. p.
Σ Lo
log
+ 33
2|
B. Proofs
B.1. Proofs of Section
B.I.I. PROOF OF THEOREM 3.1
We first analyze whether the true model m² remains in the hypothesis class for all T rounds. To see this, by Lemma A.2, for all i S, and E (7), we have
log(P? (o)) -B Σ log m (o)).
oED.
where 3 = logooo(M (0) Hence, due our construction of the next hypothesis set in Algorithm 2, with probability 1- 8/TT. m" S As the worst-case classification round does not exceed M with Assumption 1, without loss of generality, assume that T = O(M).
Next, for every tth round, we prove that S.+1 S St/S (m*) where
S (7,(mm)) = (i E Dr
m 2 Aj.
Note that with probability 1 1-8/T,
0 2
log (o))
log (P. nh (o)) 2 -3,
oED,
oED,
for all E S,. From Lemma A.3, for all i S1+1. by taking union bound, it must satisfy that
pst m PT(()
(0) > 2.Nll ( p ) 33,
B
2 log
DE
where the first inequality holds due to our construction of S,+1. Thus, for E S441 we must have
23
Vi E S
Naw
12

---

A Classification View Meta Learning Bandits
This means with Nels 2 M/8( test samples per round, S S St/S5x(m") (m²).
Finally, with our design of Te, we always choose स, such that
15 2 Cx(Ilc)+1118.
This implies with probability at least 6/T, we always have
S
S 1
CX(1e))
S
which translates to
| S
1
E
Se
I CXTTe)
2
Note that in the worst case, the ratio remains with probability less than 8/T. Let W, = (1+e))(1))))) Then 120 is super-martingale, and thus, by Lemma A.I, we have
1 (1+2 (+)aamor1))
St 1
- ;1 |Sol.
with probability at least 1- 8. Under this success event, as T 20 20 log (M/6), must have |Sy] 1.
To summarize, if we use Nos- O(x-2.. log( (8 samples per classification round for T = O(C)(IIe) log(M/6)) rounds, the algorithm terminates with the correct task identifier m² with probability at least - 5, concluding the proof.
1.1.2. PROOF OF LEMMA 3.2
Following the definition of DEC in (6), we have that
dM)) 2 max min M ((() XSS
max [A. - > (ss Pm (k))
Recall that the randomized coefficient (3) can be rewritten as the following:
Č(M)
min max min ()) LE [1(u(k) + pm)(()31)) || ( iES
and let Sade be the outer solution of the above min-max-min optimization. Now for any E A([K]), let ('r) be the that achieves
i (T) arg min Em)i(()) Se
[E (BA (1) 4 pm (k))ll-
(8)
We claim that there must exist ī(T)) Sade/ (ir ((i(((r) (TT) such that the following holds:
Bm) E [1 ()q(k) # pm (k))]] 41m-))()) [E [1 (144 (k) # pm (k))
To see this, note that
1 (k7(k) + um (b:) < ((z(k) 4 (er (k)) + (()((() + pm(k))
and then, by taking i(πz) == arg min (=)) Bx (1 (x) + p.(k))], we can verify that
E [1) + 1 (k)] < ((maa(() [B [1 (T) (b) + pm (k)]l
since |Sadel 1 and the indicator function is nonnegative. Note that for all A(Ax). by construction,
Emos(()) Baaw (M)(()) # [m]]])]] < ((M)-1
13

---

A Classification View Meta Learning Bandits
Now going back to the DEC lower-bound, have
dec,(M) 2 min max ER [A((k) - -B - (u)(( um (K))]]
*EA(K) KJ) iESadv
min max *EA(K)) iESadv
(K( (Tk)) T(k Ax)
(10)
2006 T & Ax) + (m-dl((aad))) [RAWNT (m) + E An)
(11)
where define Tл T--ik E Ar). Now for every and the corresponding Tx let i (TTx defined in (8) and i(TA)) = Swdv/ (it (Tx)). Now we either choose i (mx) if
x (m)) (b(())))
and i(Tx) in the other case. We divide into two cases.
1. a (k)) < (()))) the former case, note that for all m # it (Tx).
(r( 2 10e,
and therefore,
Σ (k())(())7(() 2 (eT & Ax).
aE (Ait m
Therefore, we have / 2 (k & AA) 5 Ax) (11).
For the second term, that
(Saa)(( [ [ (M (k), um (1:))]] (m S X X²Emai((Ssae) [B [1 (m (k), um (x))]l S (X²(M))-
Therefore, the second term becomes IT s 2 & AA) ( Ax).
2. . (x))) T Tkk (( In the latter case, repeat the same process except that take the worst-case inner-instance i i= i(TT)), we get the same inequalities.
Combining all results, we can conclude that
T- 2 (5e- 200c27)T(k & Ax) + ( 13---8C(0))) T E Ar) > 3c,
for any A[[K] with y cy min (((M)-)((MM)) for some sufficiently small c, 0. Therefore,
(M) > 3e,
concluding the proof.
1.1.3. PROOF OF THEOREM 3.3
To identify the optimal arm (so that we can play it for the majority of rounds), it must hold dec, < e. On the other hand, we have the following lower bound, which reminiscent of lower bound results in (Chen et al., 2022a) and (Foster al., 2021):
Theorem B.1. For any 8 E (0, and a regret minimization algorithms for H rounds,
Reg (MI > C2 max min ((dec,(M)) 6) H, 7)
with probability at least 5 for some absolute constant C1, C2 0.
14

---

A Classification View Meta Learning Bandits
Thus, we must have 7 - ( so that have dec,, (M) 3e for all 7 greater than this threshold. Otherwise, any algorithm must suffer from at least (mmin(eH,, A (C(M() regret with probability at least å = 11/H < c. Furthermore, since Regn 2 Regn, for any 2 Hg. it holds that for all H 2 Ho À (C()), we must suffer Reg Ω2( ( (M()))
1.1.4. PROOF OF THEOREM B.1
The proof follows Section C.I in (Foster et al., 2021) with minor modification. Let define a regret for individual instance:
Regh Σ pm (kin) 14 (Riz)-
Let Em an event such that (Reg S c17) with some sufficiently small constant e1 For any algorithm, y > and 1/H we consider, we assume that for all [M), (Em) 2 1 since otherwise the algorithm suffers from at least 7 regret with probability at least 8.
Let us fix an algorithm A such that at tdh round with previous observations H = (01,..., ...., 0t-1) where = (x,, oe Tt), and the policy at each round is decided by an algorithm π. = A(-12,, ((t-1)), Let IP be the distribution of sequential observations (0),... 0H) for rounds with bandit Vn- Following Lemmas are adapted from (Foster et al., 2021):
Lemma B.2 (Lemma A. 11 in Foster et al. 2021). For any two distributions μ. measurable space X. and any bounded real-values function X + R with 0 < (xx) S B, we have
[,,[((]]] [X(]] S + + DE(,,
In particular,
[x)) [x()] S (E, + v).
Lemma B.3 (Lemma A.13 in Foster al. 2021). For any two bandit instances V4, V/ E M.
DA P Ch E, En (
where CH 0 a sufficiently large absolute constant.
Given the lemmas, for any E A(M)) and for any algorithm that generates an adaptive policy Tes let Φ 1
H E (-11(((-1)) (note that this is a random variable), and let म == Ema [+).
Lemma B.4 (Minor Edit of Lemma C.1 in Foster et al. 2021). For any two bandit instances vi, E M,
E, Regl -1891 S CLY H
DR PH + v Di(P! B Ba (D(( +
H
We start with the following inequality for a prior w such that:
Ena= (a um([a] y Bnnww (D (Mm (mmm()) (a), um (a))]] dec,
sup
mE mE|M M
Such prior w E A(MM) must exist due to the definition of decy. Note that
H. Baaw (' (1m))) - Mm (a)) = Brn Beg (a.))) Dm [m)(a) H Enn- Reg
Wm Em Reg m21
Σ
wm
Em Reg" -1 11E H + Em Regh m 1 H
17
11
For I, we apply Lemma B.2 to get
< 3mm [Reg (1Em)] 47 Ief)) s 31Em [Rggii + 17
1pff).
15

---

A Classification View Meta Learning Bandits
For II, apply Lemma B.4 get
II $ (He+ (n) m ph) H
Em [BR~ (Mm (m) (b))]] + НБ.
Combining these inequalities, we have
Em [eggl 2 H dec, - Σ wm (enD) pi)) + V (i pit Em [Baa [D (m)())))))))))) (m pm (a))ll mi
m
+ Ee Baa (pm (a), Vm (a))) H15
On the other hand, we can apply Lemma B.3 to bound that
H
(PP mi Pm) S Cn
Σ
Em [E (n (k))]]
= CC H Em Ba
D (um
Cn ( (a)))
Plugging these results, we have
Em RegHl m)
2 H dec, H(ery VH) Σ wm E+ [D] (v (6)), un (A:))
+ + BA (v (k), um (+))]] H5.
Note that
Enn Ea ( (B)
Σ wm Ea (v (k),, vm (k))).
This implies that long as ej is sufficiently small constant and 7 2 v H, the expected lower bound is given by
E (RggT) mi > (Mcc,(M)) 8)
Proof of Lemma B.3. The general version of subadditivity lemma in (Foster et al., 2021) is stated as the following:
Lemma B.5. Let (X1, Fi), Fa) be a sequence of measurable spuces, and let (0) = I and F(() Di Fr- μ., be the laws of sequence X1,.. Xn following the sequence of (y("),... (())), (v(1), y.ng (()) respectively. Then holds that
For each i, let y(0), (0) be probability kernels from (211-11, (X(i-1),F(i-1) F()-1) to
Da(u, v) S 100 log(n) E D3(n (1111, X 1), 10 (1I1, X,-1))
4 (o. for all i, then Furthermore, if there exists a constant such that (up 1) suPo,EF witl plrne 1)
Da(u,v) < 3log(VV) D. (IXI X. wl 1l0 (1) Xi-1))I
Our construction belongs to the latter case, since the probability of observing r = 1 or T2 Os larger than 1-A any > < 1/2.
2 2 1/4 for
Proof of Lemma B.4. In our construction, for all pair of bandit instances μt, v E MI, the optimal values are the same, that is,
M ( v(k5) 0.
where kyg kn are the optimal actions for μ. v respectively. The remaining steps are identical to the proof in (Foster et al., 2021) (see their Section C.1.2), and we omit them here.
16

---

A Classification View on Meta Learning Bandits
B.2. Proofs of Section 4
B.2.1. PROOF OF LEMMA 4.1
Proof. We can rework the result (Hsu et al., 2011, Theorem 1), originally designed for the excess quadratic loss, to write
50t (d + +2 (id++2/llog/l dlog(2/0) 210g(2
Ep x Ton - x xTozal
S
N
where Ô is the ordinary least squares with N samples. Then, we just plug 6 2HMK in the expression to obtain the guarantee with a few algebraic manipulations.
B.2.2. PROOF OF THEOREM 4.2
Let us start looking at the sample complexity. Since the Algorithm 3 takes Nest samples for every arm & E [K] and simulator 1/ E M, can conclude that the statistical complexity of meta training is 1MK 1))(4HMK)
min[A] min. .22)
Assuming access to parallel simulators, the computational cost of meta training depends on the cost of executing line 12 in Algorithm which is calling Algorithm 4. The latter requires executing |S] evaluations at lines 5, 6, where |S| M, and compute the greedy step (line 3), a cost that is paid for every call to the recursive procedure (line 8). Computing the greedy step through Algorithm 5 is done in 4K AK/A* steps. Finally, the total number of nodes in the tree, which is O(M2). Putting all together we get complexity of order O(M3K/X)
bound the number of calls to the recursive procedure with
B.2.3. PROOF OF LEMMA 4.3
Proof. The result follows directly from the approximation guarantee of the greedy algorithm to build the decision tree (Arkin al., 1993), which guarantees d = Olog M 1)Cx(M), Especially, we have to prove that the previous guarantee does not degrade with our implementation, which include 4/4diiccreiization of the space of tests (see Algorithm line 4). Thanks to the separation condition (Assumption 2), can prove that every test ja(k) s b with b [0. can be replicated with at most two tests defined on the discretized space, i.., ji(k) s b with b [0. 1/2/4. Since the approximation degrades of constant factor only, the result D = Ollog M + (MI) holds.
B.2.4. PROOF OF THEOREM 4.4
Proof. To derive the upper bound on the regret, we aim to prove that the remaining task im at the end of the Explicit Classify phase corresponds, up to a small estimation error, the true test task μ² with high probability, and that the policy x² played from there in the Exploit phase corresponds to the optimal policy for the test task v" with high probability (despite the mentioned estimation error).
If we let n (2) = arg TEll" x T 0 ((m)
the optimal policy of the (true) test task, we aim to prove
Pp(# T" (x)) P"Expplicit Classify fails" V "Exploit fails") S 1/H
which we can guarantee by showing that the Explicit Classify and Exploit phases fail with probability less than 1/2H and then applying a union bound.
Let us first take the good event for the Explicit Classify phase, which means the remaining 2... a "good" estimate of the test task v²* We have that
PP("Exploit fails") = Pp
4
+ π
(12)
U x xT (o) xxx00sh 0sk
< Pp
(13)
(E(M)]AE(K]
Σ
Σ
Pp
x T
(x)
S Sx sTT00))
3
(14)
2HMK
2H
ME[M] KE(K]
KE[M] KE[K]
17

---

A Classification View Meta Learning Bandits
where we consider any possible choice of the remaining task Pm- and the test task D² write (13) from (12), apply union bound and the estimation guarantee of Algorithm 3 (see Lemma 4.1) to write (14).
Conversely, under the good event for the Exploit phase we aim to prove that the Explicir Classify phase fails with probability less than 1/2H. Since the Explicit Classify phase is actually sequence of tests, we need to bound the probability that each test fails. Formally, let J denote the number of iterations of the loop between lines 3-11 (Algorithm 6), through union bound we have
P("Explicit Classify fails") = IP
"test at iteration j fails" SEIU
U
PP at iteration j fails")
JE[J]
Now, we need to design Neis such that the test at each iteration fails with probability less than 2HJ 2 2HD where D is the depth of tree For each iteration j. take the test μ4 S b and let Neto EnE[Ne.)] Tn the empirical mean of the samples In 1/ (In, k) collected from the test task line (Algorithm 6). We need assure that the event zi falling on one side of the test while the "right" jig is the other side (see lines 6-11 of Algorithm 6) happens with small enough probability. Formally,
PPttss at iteration j fails")
= P((n S <b^ i > b+
BAN <b- A))
< P(1 iul > X)
- P(7 - μul > X/2) + P(Iix - M& > A/2)
For the second event, we invoke the estimation guarantee of Algorithm (see Lemma 4. to write P(Jã - Mul > x/2) S 2HMK S T For the first event, we need to assure that P[F Ma x/2) S मØĐ Since ςí the empirical mean of μkx by applying the Hoeffding's s inequality, we have that Ne X
2log(8HD) gives the desired guarantee.
Having demonstrated that P' (+* (*) # n (x)) holds with probability less than 1/H, we can finally write
Ne Σ
H
2D log(8HD)
Regh((M) = Ep
max kE[k]
T 0z + Ep
max T.T 0g - xTJ 0 (21)
((x)
kEIK]
X2
IN=
by taking of 0% - x (ax) in the good event, upper bounding maxke]K] Fe 0g - r2 S and JN S DNess and then
apply the approximation guarantee D = O(log M + (MI)) from Lemma 4.3 to get the result.
B.3. Proof of Auxiliary Lemmas
B.3.1. PROOF OF LEMMA A.2
The proof of MLE-based confidence set construction is by now standard and can be found in several prior works (e.g., Liu et al. 2022). We udapt the proofs from (Kwon et al., 2024) for completeness.
Proof. The proof follows Chernoff bound type of technique:
Por (o) (o)
P (o)
)
P..
Σ
log
2 E,p
log
+33
pott
pr. (o)
DED
D
LED
P. (o) )
P.T
< Pr,
exp Σ log
2 exp (9)
DE
P. (o) (3)
E,,-
exp
Σ
log
pr.
DEED
The last inequality is by the Markov's inequality. Note that random variables are in the trajectory dataset D, and
(P(()) )
En
Σ log
(D( s 0.
P (o)
LoED
18

---

A Classification View Meta Learning Bandits
Furthermore,
(0) P (o) ))]
Eu- HOED PE (0) Py. (o) = 1.
En-
exp
log
LEDD
Combining the above, taking union bound over E M. letting B log(M/6), with probability 1 6, the inequality in Lemma A.2 holds.
B.3.2. PROOF OF LEMMA A.3
Proof. By the TV-distance and Hellinger distance relation, for any 4, and [H],
Po (o)
(o)
D2 (P:: P.)) Eeony
S log
Eanpy
P... (0)
p (o)
By the Chernoff bound,
(o) pr. (o)
(o( Pr.. (0)
Py- Σ log
z |D] log Eowpy
+
MED
exp EoED log
(o)
P.-(o)
< Eyy
exp(-3)
exp |D] log Eonty.
(o]
TOEDY/ V
(0) Fr (o)
E,--
exp(-3) exp(-3),
Brwwy
(r( P.. (T)
where in the last line, used the independent property of samples. Thus, again by setting log(MM6)), with probability at least 1 17, we have
P. ())
[D]
D2
pr.
<
Σ
log
+ 3
w1
2
PT.
oED
1
PT (o)
1
P. (0) po. (0)
log
log
3,
p. (o)
oED
for all & E [K] and v M.. Now we can apply Lemma A.2, and finally have
p.t
log
338
2|D1
Pr.. (o)
oED
19

---

A Classification View Meta Learning Bandits
C. Additional material
C.1. Greedy algorithm
Algorithm 5 provides the pscudocode tractable procedure to compute the greedy test for Algorithm through
d/ddiiccrtizattin of the space of thresholds
Algorithm 5 Greedy Test
1: input set of tasks S
2: for [K] do
Define s (b) = {v E (((k < b- 2/2
4: Define 5-(b) (b) = (i E S ((k) > b- 2/2)
5: Compute (b( = max 1/x4 min(|S* |S (6)I)
end
7: Extract (k: b) = arg [((k (b)
output greedy test ({((k) b)
C.2. DT-ECE
Algorithm provides the pseudocode of the DT-ECE algorithm, which implements ECE (Algorithm 1) for a misspecified set of tasks M with a decision tree classifier.
Algorithm Decision Tree Explicit Classify then Exploit
I: input of tasks M, decision tree tree(M), Nete 2
Initialize Su M.
Explicit Classify
3: while |S&] > 1 do
4: Extract test (fu < b) = (ree(S;)
5: DD +- Nes i..dd samples drawn with = k
6: if
Nak Erep," b then
7: Get S tree(S,, true)
9: Get S.+1 + tree(S, false)
10: end if
11:
end while
12: Extract the classified task m St and execute #" (*(x) arg mrgmmxene Pm (x, k) for the remaining steps
Exploit
20


Reviews:
[{"review_id": "X3pnWT4r0E", "reviewer": "Reviewer_1Rko", "summary": "This paper presents a novel classification - based approach to meta - learning bandits. Contextual multi - armed bandits are widely used for sequential decision - making, but common bandit algorithms have issues like high regret and lack of interpretability.\n\nThe authors consider a meta - learning setting of latent bandits with a separation condition. They introduce a classification - coefficient to measure the complexity of the learning problem. The Explicit Classify then Exploit (ECE) algorithm is proposed, which classifies the test task and exploits the optimal policy of the classified task. To make the algorithm more practical, the Decision Tree ECE (DT - ECE) is developed. It is robust to misspecifications, only accesses samples from the context distribution, and provides an interpretable exploration plan. Experiments show that DT - ECE performs well compared to current bandit approaches.\n\nIn conclusion, this classification view offers a new way to design interpretable and efficient exploration plans, and may inspire future research in more general problem settings.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We want to thank the reviewer for their feedback. We are replying to their comments below.\n\n**Claims and evidence**\n\nInterpretability is a crucial motivation of our paper and we want to make sure we are on the same page with the reviewer on this. Especially:\n  - **Interpretability of bandit algorithms**: Translating a notion from supervised learning to the bandit setting, we say that exploration is interpretable if it can be represented through a decision tree with *small depth* (see Bressan et al. 2024 https://proceedings.mlr.press/v247/bressan24a Def. 2). Our work is the first to establish bounds on the depth of the decision tree for exploration (Lemma 4.3)\n  - **UCB and TS are interpretable**: UCB and TS may also be represented through a decision tree, but its depth can be as large as the number of rounds. According to this notion UCB and TS are *not interpretable*. See an example of how our algorithm builds a compact decision tree (https://anonymous.4open.science/r/anon_icml_rebuttal-90C9/empirical_tree.pdf from the experiment of Figure 4a) whereas an analogous tree for UCB or TS exploration is too large to be visualized\n\n**Methods and evaluation criteria**\n\nGreat point! Storing the full decision tree requires additional $M 2^{C^* (\\mathbb{M})} \\leq M 2^M$ space in the worst-case, which may be impractical in applications where the number of tasks $M$ is huge. In those cases, the tree can be traversed *online* without pre-computing it (like in Algorithm 1) with negligible additional space complexity. We will add space complexity and considerations on balancing interpretability and memory requirements in the updated manuscript.\n\n**Theoretical claims**\n\n“Each bandit might be at a different stage of convergence” we are not sure we understand the reviewer’s concern here. Note that we interact with only one bandit at test time. Moreover, stationarity is orthogonal to whether the reward distributions are stochastic or adversarial. We target the stationary stochastic setting, just like in the previous literature of latent bandits (with the exception of Hong et al 2020b), aiming for fast and interpretable exploration. This makes the approach *more* practical (than previous works) in some applications, e.g., the candidate bandits represent user “types” in a recommendation system: It is often reasonable to assume that a user doesn’t change “type” during the interaction. We agree with the Reviewer that some other applications are inherently non-stationary and extending our results is a non-trivial direction for future works.\n\n**Experimental design**\n\nWhile we developed a method intended for practical settings, we remark that the core contribution of the paper is conceptual. However, to  support practicality of our method, we will add an additional experiment in which we compute the decision tree on the MovieLens dataset (https://grouplens.org/datasets/movielens/), similarly to Hong et al 2020a (see their Sec 5.2). Users are first clustered into types, based on historical data. Then, the decision tree that we learn essentially prescribes what movies to recommend in order to classify the type of an unknown user, to then maximize their reward by providing recommendations specialized for the classified type.\n  - **Super-parameters are fixed.** We considered different values for the separation parameter, number of arms and bandits. Is there any other parameter the reviewer would like to see explored?\n  - **Baselines.** The aim of the experiments is not to outperform any prior bandit algorithm, as our is the first method that is *interpretable* (in the sense above) and thus competes in a different field. If the reviewer thinks there is a baseline that is relevant to the latter field, we will be happy to include a comparison.\n\n**Essential references**\n\nThanks for pointing out additional relevant work. We will be happy to include them in the paper with appropriate discussion. Qi et al and Xie et al are interesting but tackle orthogonal problems. S&D 2021 meta learn exploration for contextual bandits, which is similar in nature to our setting. Their algorithm, MELEE, trains exploration by imitating an expert (optimal exploration) in simulation. There are crucial differences:\n  - We do not assume access to an expert during training, but only to simulators\n  - MELEE is not interpretable according to our notion (see above), as we cannot bound the depth of a decision tree representing its policy\n  - MELEE’s regret goes to zero asymptotically, but the regret rate is implicit in their result\n\n**Other weaknesses**\n\nThanks for letting us know that the symbols are sometimes hard to grasp. We will make a careful revision of all the symbols and to convey enough intuition. See the comment for all the reviewers in the response to Reviewer HVdH for an intuitive explanation of the coefficient $C_{\\lambda} (M)$.", "claims_and_evidence": "While the authors aim to enhance the interpretability of bandit algorithms, their motivation lacks sufficient depth. The claim that bandit algorithms lack interpretability is controversial, as these algorithms, grounded in probability theory with well - defined mathematical assumptions, already possess a form of inherent interpretability. The paper fails to adequately justify the need for further interpretability. To strengthen the motivation, more real-world examples are essential.", "methods_and_evaluation_criteria": "Considering only regret might be insufficient. In real-world applications, other factors like space complexity, which will be worse due to the tree, could also be important evaluation aspects that are not fully explored.", "theoretical_claims": "The paper's assumption of a stochastic environment when optimizing multiple candidate bandit instances is a flaw. In reality, these bandits often operate in non-stationary conditions. Each bandit might be at a different stage of convergence, leading to diverse current performances. Could authors explain this point?", "experimental_designs_or_analyses": "The experimental datasets are simplistic, consisting entirely of synthetic data with relatively fixed parameters. This simplicity raises concerns about the generalizability of your findings. Real world problems are often complex and variable, and the lack of diverse and realistic datasets means that it's difficult to assess how your proposed methods would perform in practical scenarios. \n\nThe absence of scalability experiments is a significant drawback. The super-parameters of setting are fixed.\n\nRegarding the comparison with baseline methods, limiting the comparison to only one or two baselines is insufficient. There are many established methods in the meta bandit literature, and not comparing your approach with a wider range of them makes it difficult to position your work within the existing research landscape. A more comprehensive comparison would provide a better understanding of the relative strengths and weaknesses of your proposed algorithms.", "relation_to_broader_scientific_literature": "Bandit study is related to many ML fields.", "essential_references_not_discussed": "Qi Y, Ban Y, Wei T, et al. Meta-learning with neural bandit scheduler[J]. Advances in Neural Information Processing Systems, 2023, 36: 63994-64028.\n\nSharaf A, Daumé III H. Meta-learning effective exploration strategies for contextual bandits[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(11): 9541-9548.\n\nXie M, Yin W, Xu H. AutoBandit: A Meta Bandit Online Learning System[C]//IJCAI. 2021: 5028-5031.", "other_strengths_and_weaknesses": "The paper is replete with a plethora of symbols, which, while essential for the mathematical rigor of the research, lack sufficient explanation of their importance. For example, the \\(C_{\\lambda}(\\mathbb{M})\\). Why it is a core contribution? Explanation for the meaningful is better to present the symbols.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "", "extra_scores": {}}, {"review_id": "JnliRxsQ0m", "reviewer": "Reviewer_HVdH", "summary": "The authors address a meta-linear latent contextual bandit setting, where there are M total possible bandit settings, and where there is separation between these M settings. Authors thus propose a classification view that leverages this separation: first, classify the test task as one of M settings; then, perform the greedy policy assuming the test task is correctly classified (\"ECE\": Explicit Classify then Exploit). Authors prove properties about the proposed method when assuming full knowledge of the bandit settings, including a regret bound that uses a novel measure of complexity. Authors also propose a practical implementation of ECE with decision trees. The resulting exploration policy is interpretable, which can be an important feature in practice. Authors also prove properties of the practical method. Authors demonstrate that the performance of the proposed method is on par with versions of TS and UCB, which are not interpretable.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We are glad to hear that the reviewer appreciated our work. We thank them for their thoughtful comments, useful suggestions, and for pointing out typos. We will make use of them to improve the manuscript. We address their questions below.\n\n**Value of $N_{cls}$ in the experiments**\n\nWe used $N_{cls} = C / \\lambda^2$  in all the experiments, where $C$ is a constant. We set $C = 4$ after trying $C = 2, 4, 8, 16$ (results are not particularly sensitive to this value). Moreover, we implemented an adaptive sampling strategy that checks the confidence of the test at each sample, so that the sampling ends whenever the desired confidence is reached or $N_{cls}$ samples have been taken. The adaptive sampling also didn’t affect results substantially, but it makes the algorithm slightly more efficient in some settings. We thank the reviewer for pointing out that this information is missing in the text. We will add a specific section with experimental details to the Appendix. \n\n**Other comments:**\n  - Why is $C (M) < C^* (M)$ in (5)?\nThank you for the opportunity to clarify. First, we provide below an detailed explanation of $C (M)$, which can help to understand the proof. Proof: This is a standard argument in decision trees that $C(M)$ is a lower bound to $C^* (M)$. Consider any subset of hypotheses $S$, and when starting from this subset, let the maximum number of hypotheses that we can rule out each round is at most $N$. Then, the depth of any deterministic decision trees with the subset $S$ must be at least $S/N$. Since $C^* (M)$ is the depth of deterministic trees for a larger set of hypothesis, $S/N < C^*(M)$. This holds for all subsets of $M$, hence $C(M) < C^*(M)$. \nFollowing reviewer’s suggestion, we will add this sketch of the proof of eq. 5 in the Appendix.\n  - *In Section 3.1 it would improve clarity to explain that the non-optimal arms are such that for $i \\neq j$ for which $\\mu_i (a) = (1 + \\lambda) / 2$ and $\\mu_j (a) = (1 - \\lambda) / 2$ (I assume this is true based on the rest of the section, but it is not explicitly stated.)*\nThe reviewer is right! This is implied by the separation assumption (Asm. 1) but we agree with the reviewer it is very implicit. We will explicitly mention this in the text.\n\n\n------\n\n# **For all the Reviewers**\n\n**Intuitive explanation of $C_\\lambda (\\mathbb{M})$**\n\nBased on all the reviews, we understand that our exposition of $C_{\\lambda} (M)$ could be improved with more intuition. We want to provide an intuitive explanation of its meaning here. We hope that the additional clarity will make the reviewers better appreciate this important contribution.\n\nInformally, the value of $C_\\lambda (\\mathbb{M})$ measures how much information we gain from a single split of the worst-case node of the decision tree (small value means more information). To see this, let us look at the math:\n\n$$C_\\lambda (\\mathbb{M}) := \\max_{S \\in 2^{[M]}} \\min_{\\pi \\in [K]} \\max_{i \\in S} \\frac{|S|}{|S_{\\lambda}^\\pi (i)|}$$\nLet us unpack each term. $S$ is a set of candidate bandits and $i$ stands for the true bandit within $S$. $\\pi$ is an arm we *test* on the true bandit. $S_{\\lambda}^\\pi$ is the subset of $S$ that we can eliminate from the set of candidates by pulling $\\pi$ enough. Thus, the ratio $|S| / |S_{\\lambda}^\\pi|$ measures the amount of information we can gain from this split. In the extreme cases:\nWe eliminate a single bandit from $S$, so that $C_{\\lambda} (\\mathbb{M}) = M$ is large (little information gained)\nWe eliminate half of the bandits in $S$ and $C_{\\lambda} (\\mathbb{M}) = M / (M/2) = 2$ is small (a lot of information gained). Note that we cannot reduce $C_{\\lambda} (\\mathbb{M})$ by eliminating more than half of the candidates, as $i$ is chosen worst-case to select the largest set after the split.\n\nWe will add this intuitive explanation together with extreme cases and visualizations in the updated manuscript.", "claims_and_evidence": "Theoretical claims:\n- Theorems and lemmas have proofs in the appendix. Due to limited time, from spot checking, Theorem 3.1 seems to have no (serious) issues. \n- Occasionally claims are made casually in the text that cite another work, but readers could benefit from a proof sketch in the appendix (e.g. Eq 5). \n\nEmpirical:\n- The proposed method performs on par with versions of TS and UCB: this looks fine to me.", "methods_and_evaluation_criteria": "Methods: \n- The methods (with and without full knowledge of $\\mathcal M$) seem very reasonable to me, given the assumed setting. \n- I am curious what kinds of realistic settings the assumptions could correspond to, and especially ones where the proposed method should perform particularly well. \n- I am curious about what values $N_{cls}$ takes on in practice. \n\nEvaluation: \n- The experiments are done on simple settings but the paper contribution is primarily theoretical. \n- One could say that because the proposed method is interpretable, unlike existing baselines, it adds value even if it does not outperform. This would be true assuming there do not exist other tree-based exploration policies for this setting.", "theoretical_claims": "I checked the proof of Theorem 3.2 for correctness and I did not find (serious) errors.", "experimental_designs_or_analyses": "Yes, I read over the experiments section and it looks sensible.", "relation_to_broader_scientific_literature": "This paper proposes using tree-based classification for interpretable exploration in a meta-learning contextual bandit setting where the total number of settings is fixed ($M$) and the settings have separation. Perhaps I am not that familiar, but I don't often see meta-bandit papers with separation and with tree-based classification.", "essential_references_not_discussed": "There are many papers that are tangentially related that I am familiar with (e.g. other meta-bandit papers) but I wouldn't consider any of them to be essential for discussion.", "other_strengths_and_weaknesses": "Strengths\n- The paper is clearly written. \n- The proofs are well-organized and concise. \n- The paper does not overpromise or overhype. \n\nWeaknesses\n- The linear bandit assumption is strong. However, such assumptions are also common.", "other_comments_or_suggestions": "- Typos in the abstract, e.g. \"asses\" and \"When human design strategies\", and also elsewhere, e.g. \"For instance, to minimize the number of times a treatment different from the optimal one is administered to a patient\" is not a full sentence. \n- Algorithm 1 line 4 should be argmax rather than max\n- It seems like / is used to denote set-minus (e.g. line 252, 587), which in my impression is less common than \\.\n- In Section 3.1 it would improve clarity to explain that the non-optimal arms are such that for $i\\neq j$, there is some arm $a$ for which $\\mu_i(a)=(1+\\lambda)/2$ and $\\mu_j(a)=(1-\\lambda)/2$. (I assume this is true based on the rest of the section, but it is not explicitly stated.)\n- I think line 815 does not follow from line 812, but line 818 is still true. The KL should not disappear on line 815. \n- Where does $\\hat m_t$ come from in line 593? \n- Why is $C(M)\\leq C^*(M)$ in (5)?\n- In the abstract, part of the motivation is \"When human design strategies, they aim for the exploration to be *fast*, since the patient’s health is at stake\". This phrasing suggests something more urgent / is measured via something other than better asymptotics. I think this is a minor point.", "questions_for_authors": "1. What is $N_{cls}$ in the experiments?", "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": "", "extra_scores": {}}, {"review_id": "esO40Rj6LP", "reviewer": "Reviewer_hH2x", "summary": "This paper studies a meta-learning approach to multi-armed bandits (MAB), where multiple bandit instances (tasks) are drawn from an unknown prior distribution. The key contribution is formulating meta-learning bandits as a classification problem, leveraging a novel complexity measure called the classification coefficient.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their insightful comments. We provide below detailed replies.\n\n**Questions for authors**\n\n   1. Our analysis and experiments consider overlapping tasks [for “overlap”, we mean the bandits may have the same, or similar, reward distribution for some of the arms/contexts. If the reviewer was thinking of a different kind of overlap, we kindly ask them to please elaborate more on this]. The parameter $\\lambda$ controls the degree to which at least one arm distribution *does not overlap* in any pair of bandits. Since the algorithm uses $\\lambda$ to make the tests statistically robust, it suffers from the same misclassification rate with any $\\lambda$, whereas the regret degrades as $O(\\lambda^{-2})$ (see Theorem 3.1, 4.4)\n   2. Note that we also consider a setting where tasks are *not known* to the algorithm, which estimates them through samples (Section 4.1). The reviewer is right that the set of tasks is *fixed* in the paper: We do not provide results for generalization to tasks that are not seen in training. Arguably, generalization depends on “how” the test tasks differ from the training tasks. We conjecture that similar results could be obtained for the *lenient regret* (see https://arxiv.org/abs/2008.03959) when the test task is an $\\epsilon$-perturbation of a training task. For more general discrepancies between training and test, the algorithm shall be re-designed to allow for additional test-time exploration, which is a nice direction for future works.\n   3. We proved that $C_{\\lambda} (\\mathbb{M})$ captures the complexity of an instance of our setting with both a lower bound (Theorem 3.3) and an upper bound (Theorem 3.1).  This implies that $C_{\\lambda} (\\mathbb{M})$ is *as good as any other* complexity measure for this *specific* setting: Finite collection of separated bandits. For the latter setting, there might be other complexity measures that are equally good (we are not aware of). In other settings, there might be better complexity measures.\n\n**Lower bound**\n\nWe actually provide a lower bound where a factor $C_\\lambda (\\mathbb{M})$ appears explicitly (see Theorem 3.3 and discussion thereafter). We thank the reviewer for making us realize that the lower bound is not highlighted enough. We will make this result more central in the updated manuscript.\n\n**Ablation study on the effect of separability**\n\nReviewer is mentioning a few times that an analysis of the effect of $\\lambda$ on empirical results is missing. We hear their concern: We will report in the Appendix more results for different $\\lambda$ values. What we noticed from our experiments is the same effect that one can see by squinting at Figure 4 (a, b). In 4a, $\\lambda$ is 0.4 and the elbow in the DT-ECE is very sharp. In 4b, $\\lambda$ is 0.04 and the elbow is a lot smoother. With smaller $\\lambda$ it takes more time to traverse the tree, both because each test requires more samples and the tree might be deeper.\n\n**Experimental design**\n\nWe agree that experiments on real-world data better supports real-world applicability. We will add to the manuscript an experiment on movie recommendations with the MovieLens dataset (https://grouplens.org/datasets/movielens/), on the same line of the MovieLens experiment in Hong et al 2020a (see response to R. 1Rko \"experimental design\").\n\n**Other weaknesses:**\n\n*“ECE relies on decision trees for classification, which may not scale well in high-dimensional settings or when task distributions are complex”* We recall that the regret of ECE is not affected by the dimensionality of the problem (see Theorem 3.1). However, we believe the Reviewer means something else here: The additional complexity of computing and storing the decision tree. The computational complexity is polynomial in both $d$ (dimensionality) and $M$ (size of the set of tasks), where the factors of $d$ disappear when the tasks are known. The space complexity is $M 2^{C^* (\\mathbb{M})} \\leq M 2^M$, which may become intractable for a large set of tasks. In those cases, the tree can be traversed *online* without pre-computing it (like in Algorithm 1) with negligible additional space complexity. We will add space complexity and considerations on balancing interpretability and memory requirements in the updated manuscript.\n\n**Intuitive explanation of coefficient $C_\\lambda (\\mathbb{M})$:**\n\nWe thank the reviewer for pointing out that the definition of the classification coefficient is difficult to understand. See the comment for all the reviewers in the response to Reviewer HVdH for an intuitive explanation.\n\n**Insufficient experimental visualizations:**\n\nFollowing the Reviewer’s suggestion, we will add visualizations of the decision trees learned by our algorithm in the Appendix. As an example, we provide the one for Figure 4a at https://anonymous.4open.science/r/anon_icml_rebuttal-90C9/empirical_tree.pdf. Especially, note the short depth of the tree even for a hard instance that maximizes $C_\\lambda (\\mathbb{M}) = M$.", "claims_and_evidence": "Yes, most claims made in the submission are supported. However,\n\n1.  There is no lower bound analysis to show that the classification coefficient is the best or tightest complexity measure for this setting. The theoretical justification for why this measure is superior to alternative complexity metrics (e.g., information gain in latent bandits, KL divergence of reward distributions) is missing.", "methods_and_evaluation_criteria": "The proposed method is well-motivated. However, there is no analysis of how regret scales with increasing task diversity or task ambiguity.", "theoretical_claims": "The high-level proof strategy follows standard approaches: First bound the number of rounds required for correct classification; Then analyze regret contributions from both classification and exploitation phases. Mostly correct, but the paper does not provide a lower bound to show whether this regret bound is tight or optimal.  And the paper does not analyze cases where tasks are not well-separated, which could impact the validity of theoretical guarantees.", "experimental_designs_or_analyses": "1. The experiments only use synthetic datasets, which are useful but do not demonstrate real-world applicability. The task distributions and separability conditions are artificial, making it unclear how well the method generalizes to practical applications. \n\n2. The paper does not test real-world recommendation, healthcare, or RL-based MAB tasks, where meta-learning could provide significant benefits.\n\n3. The theoretical results depend on task separability $\\lambda$, but the paper does not systematically evaluate how different levels of \n$\\lambda$ affect regret.", "relation_to_broader_scientific_literature": "The approach aligns with previous work in latent bandits and meta-RL, where task identification plays a crucial role. Meta-learning in bandits aims to reuse knowledge from past tasks to improve future decision-making. Alternative approaches, such as latent variable models, clustering, or embedding-based meta-learning, are not explored.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Other Strengths And Weaknesses:\n\n1. The paper introduces the Explicit Classify then Exploit (ECE) algorithm, which consists of two phases: a. The algorithm first identifies the task by collecting data from different arms and using a decision-tree-based classification method. b. Exploitation Phase: Once the task is classified, the algorithm uses the optimal arm selection strategy corresponding to that task, minimizing exploration regret.\n\n2. The paper introduces a classification-based perspective for meta-bandits, which is novel compared to traditional Bayesian or clustering-based approaches.\n\nOther Weaknesses:\n\n1. ECE relies on decision trees for classification, which may not scale well in high-dimensional settings or when task distributions are complex.\n\n2. No ablation studies to understand the effect of task separability $\\lambda$ or decision tree depth on classification accuracy and regret.", "other_comments_or_suggestions": "1. The intuitive explanation of the classification coefficient \\( C_\\lambda(M) \\) is unclear and difficult to understand. \n\n2. The method is introduced in a straightforward manner, lacking motivational analysis, which makes it feel like a direct application of classification methods. \n\n3. Additionally, there is insufficient experimental visualization, such as task classification processes and decision boundaries.", "questions_for_authors": "1. No discussion on what happens when tasks overlap—does misclassification degrade performance significantly?\n\n2. The algorithm assumes a fixed set of known tasks—how does it generalize to new, unseen tasks?\n\n3. Is $C_{\\lambda}(M)$ provably the best complexity measure for task classification in meta-bandits, or could a better bound be derived?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a classification-based approach to meta-learning in contextual bandits, introducing an interpretable decision-tree-based algorithm and a novel complexity measure, the classification coefficient $C_\lambda(\mathbb{M})$, to characterize regret.

Reviewers raised concerns about the limited empirical validation and questioned the necessity of the new interpretability framing. However,  authors provided clear responses, offered intuitive explanations of theory, and committed to adding real-world experiments and improved exposition. the paper’s strengths lie in its conceptual novelty, theory, and formal treatment of interpretability.

I encourage the authors to incorporate the promised experimental additions and further clarify technical concepts to strengthen the final version.
Decision: Accept (poster)