Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
Authors: Aleksandrs Slivkins
Yunzong Xu
Shiliang Zuo
Venue: NeurIPS 2025 poster ()
Keywords: Multi-arm bandits
contextual bandits
structured bandits
greedy algorithm
regret
Primary area: theory

Abstract: We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time.
Our characterization identifies a partial identifiability property of the problem instance as the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy—\emph{any} algorithm will succeed (in the same sense as above), provided it satisfies a mild non-degeneracy condition. Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback. Examples demonstrating broad applicability and extensions to infinite reward structures are provided.

Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
Aleksandrs Slivkins Microsoft Research, New York City sliviinseiicrooff.. com
Yunzong Xu University of Illinois Aibana-Champpan xyzeillinois.ed
Shiliang Zuo
University of Illinois Urbana-Champaige szuo3@illinois edu
Abstract
We study the greedy (exploitation-only algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time. Our characterization identifies partial identifiability property of the problem instance the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy-any algorithm will succeed (in the same sense above), provided it satisfies mild non-degeneracy condition. Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback. Examples demonstrating broad applicability and extensions to infinite reward structures are provided.
Introduction
Online learning algorithms often face uncertainty about the counterfactual outcomes of their actions.
To navigate this uncertainty. they balance competing objectives: exploration, making potentially suboptimal decisions to acquire information, and exploitation, leveraging known information to maximize rewards. This trade-off central to the study of multi-armed bandits (Slivkins, 2019 Lattimore and Szepesvári, 2020), a foundational framework in sequential decision-making.
While exploration is central bandit research, it presents significant challenges in practice, esp. when an algorithm interacts with human users. First, exploration can be wasteful and risky for the current user, imposing a burden that may be considered unfair since its benefits primarily accrue to future users. Second, exploration adds complexity to algorithm design,and its adoption large-scale applications requires substantial buy-in and engineering support compared to system that only exploits [Agarwal et al., 2016 [017]]. Third, exploration may be incompatible with users' incentives when actions controlled by the users. E.g., an online platform cannot force users to try and review new products; instead, users gravitate toward well-reviewed or familiar options [Keemer et al. 2014
A natural alternative is the greedy algorithm (Greedy), which exploits known information at every step without any intentional exploration. This approach sidesteps the aforementioned challenges and often better aligns with user incentives. In particular, it models the natural dynamics in online
1. Enforcing exploration in such settings is very challenging (Kemer et al. [014] and follow-up work, see Slivkins [2023] for overview). While exploration can be made incentive-compatte doing involves considerable performance and/or monetary costs and additional complexity. More importantly, it hinges upon substantial (even standard) assumptions from economic theory.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

platform where each user acts in self-interest, making decisions based on full observations of previous users' actions and outcomes, e.g., purchases and product reviews [Acemoglu et al. 2022].
Despite its simplicity and practical appeal, Greedy is widely believed to perform poorly. This helief is deeply ingrained in the bandit literature, which overwhelmingly focuses on exploration as necessary ingredient for minimizing regret. A key motivation for this focus comes from well-known failure cases in unstructured K -armed bandits. A classic example is as follows: "Suppose the reward of each arm follows an independent Bernoulli distribution with a fixed mean, and Greedy is initialized with a single sample per arm. If the best arm initially returns 0 while another arm returns 1, Greedy permanently excludes the best arm."
However, beyond such examples, the broader picture remains murky, especially for the widely-studied structured bandits- - bandit problems with a known reward structure (e.g., linearity, Lipschitzness, convexity) - where observing some actions provides useful information about others. Formally, reward structure restricts the possible reward functions that map arms to their mean rewards. Reward structures reduce the need for explicit exploration, making the bandit problem more tractable. For some of them, Greedy in fact succeeds, e.g., two-armed bandits with expected rewards that sum up to a known value. The literature provides a few examples of failure for some specific (one-dimensional, linear) reward structures, and a few non-trivial examples of success (e.g., for linear contextual bandits); see more on this in Related Work. Likewise, large-scale experiments yield mixed results: some settings confirm the need for exploration, but others indicate that Greedy performs well (Bietti et al. 2021]. This contrast raises a fundamental question: When-and why does Greedy fail or succeed?
Our Contributions. We work towards the missing foundation for structured bandits: a general theory of Greedy. Our main result allows finite, but otherwise arbitrary reward structures. We provide a complete characterization of when Greedy asymptotically fails (incurs linear regret) vs when it succeeds (achieves sublinear regret). Our characterization applies to every problem instance, resolving it in the positive or negative direction, not (just) in the worst case over a particular reward structure. The negative results are of primary interest here, as they substantiate the common belief that Greedy performs poorly, and the positive results serve to make the characterization precise.
A key insight is identifying a new "partial identifiability" property of the problem instance, called self- identifabiiliy, as a necessary and sufficient condition for the asymptotic success. reff-identifiability asserts that, given the reward structure, fixing the expected reward of suboptimal arm uniquely identifies it as suboptimal. We prove that Greedy achieves sublinear regret under self-identifiabbiityy. and suffers from linear regret otherwise. The negative result is driven by the existence of decoy: informally, an alternative reward model such that its optimal arm is suboptimal for the true model and both models coincide on this arm. We show that with some positive probability, Greedy gets permanently stuck on such a decoy, for an infinite time horizon. For the positive result, Greedy succeeds (only) because celf-identifiabilityy makes the problem instance intrinsically "casy". In fact, this success is not due to any particular cleverness of Gr Greedy: we show that any reasonable algorithm (satisfying mild non-degeneracy condition) achieves sublinear regret under celf-identifiabilityy
Our characterization allows for essentially an arbitrary interaction protocol between the algorithm handle the model of "decision-makee making with structured observations" (DMSO, Foster et al.] (2021)). which allows for arbitrary auxiliary feedback after each round. This model subsumes contextual bandits, combinatorial semi-bandits, and bandits with graph-based feedback, as well as episodic reinforcement learning. Before moving to this full generality, our presentation focuses on contextual bandits, where we obtain quantitatively stronger guarantees (Section{)) 4. and "vanilla" bandits as a paradigmatic case for building key intuition and cleaner definitions (Section 3).
and the environment (Section 5). Specifically,
We apply our machinery to several examples, both positive and negative (Appendix D). We demon- strate that most infinite structures of interest admit meaningful finite analogs via discretization. We find that Greedy fails in linear bandits, Lipschitz bandits and "polynomial bandits" (with arms in R and polynomial expected rewards), and does for almost all problem instances. For linear contextual bandits, Greedy succeeds if the context set is "sufficiently diverse", but may fail if it is "jow-dimensional.. For Lipschitz contextual bandits, Greedy behaves very differently, failing for almost all instances. One informal takeaway is that Greedy fails as a common case for most/all bandit structures of interest, whereas for contextual bandits it can go either way, depending on the structure. The success of Gr Greddy appears to require context diversity and a parametric reward structure.
2

---

The second main result of this work concern infinite (e.g., continuous) reward structures (Section ( While our earlier analysis gave a sharp "if and only if" characterization for finite reward structures, such a complete characterization is more challenging to obtain for infinite ones. To make progress, we provide a characterization parameterized by a notion of "margin" (separating instances for which the positive result applies from instances for which the negative result applies), with guarantees that deteriorate as the margin vanishes. Subject to this margin, our result handles arbitrary infinite reward structures. It applies to structured bandits with finite action sets, requiring stronger notions of self-identifiabiliyy and decoy existence (parameterized by the margin), as well as new analysis ideas.
Discussion.
The distinction between linear and sublinear regret is a standard "first-order" notion of success vs failure in bandits. Our positive results attain logarithmic, mnstance-dependett regret rates, possibly with a large multiplicative constant determined by the reward structure and the instance. Our negative results establish a positive (but possibly very small) constant probability of a "failure event" where Greedy gets permanently stuck on decoy, for an infinite time horizon. Optimizing these constants for an arbitrary reward structure appears difficult. However, we achieve much better constants for the partial characterization in Section
The greedy algorithm is initialized with some warm-up data collected from the same problem instance (and it needs at least 1 warm-up sample to be well-defined). Our negative results require exactly one warm-up sample for each context-arm pair. All our positive results allow for an arbitrary amount of initial data. Thus, our characterization effectively defines "success" as sublinear regret for any amount of warm-up data, and "failure" as linear regret for some amount of warm-up data.
We assume that Greedy is given a regression oracle: a subroutine to perform (least-squares) regression given the reward structure. As in "bandits with regression oracles" (referenced below), we separate out computational issues, leveraging prior work on regression, and focus on the statistical guarantees.
Related Work. Bandit reward structures studied in prior work include linear and combinatorial structures [e.g., Awerbuch and Kleinberg 2008 McMahan and Blum 2004| György et al. 2007
Cesa Bianchi and Lugosi 2012), convexity le.g., Kleinberg |0040|00aaaa Flaxman al. [205 Bubeck
ct al. 2017]. J and Lipschitzness [e.g. Kleinberg 2004| Kleinberg et al., 2008 Bubeck et al. 2011],
as well some others. Each of these long line of work on its own, with extensions to contextual bandits [e.g.. [i et al. 2010, Slivkins 2014). There's also some work on bandits with arbitrary 2011 Combes et al. 2017 Jun and Zhang 2020 Degenne al.) 2020
reward structures Amin et al.
Parys and Golrezaei 2024), and particularly contextual bandits with regression oracles le.g,, Agarwal
al. 2012 Foster al. 2018 Foster and Rakhlin 2020 Siiccii and Xu] [022]] For more
background, see books Slivkins
2019]. Lattimore and Szepesvári [2020] Foster and Rakhlin 2023
For Greedy, positive results with near-optimal regret rates focus on linear contextual bandits with diverse/smoothed contexts [Kannan et al., 2018 Bastani et al., 2021 Raghavan et al., 2023 Kim and Oh 2024). Both context diversity and parametric reward structure are essential. Our positive results for the same setting are incomparable: more general in terms of context diversity assumptions, but weaker in terms of the regret bounds. (This line of prior work does not contain any negative results.) Greedy is also known to attain of o(T) regret in various scenarios with a very large number of near-optimal arms [Bayati et al. 2020 Jedor et al. 2021
Negative results for Greedy are derived for "non-structured" K-armed bandits: from trivial extensions of the lingle-sample-pers of failure probability [Banihashem et al. 20233. to various "near-greedy" algorithms / behaviors, both "frequentist" and "Bayesian" (same paper). Negative results for non-trivial reward structures concern dynamic pricing with linear demands [Harrison et al. 2012 den Boer and Zwart 2014] and dynamic
example mentioned above, to an exponentially stronger characterization
control in generalized linear model [Lai and Robbins 1982 Keskin and Zeevi 2018 Banihashem ct al. [003]] also obtain negative results for the Bayesian version of Greedy in Bayesian bandits, under certain "full support" assumption on the prior"
2 Preliminaries: structured contextual bandits (StructuredCB)
We have action set A and context set X. In each round t = 1,2, ... a context E X' arrives, an algorithm chooses an action (arm) a E A, and a reward r; E R realized. The context is drawn
2. E.g., for Bayesian bandits with > vT arms, where the arms' mean rewards are sampled uniformly.
3. Essentially, the prior covers all reward functions {arms) [0, with probability density at least > 0.
3

---

independently from some fixed and known distribution over X. The reward re is an independent draw from a unit-variance Gaussian with unknown mean f (z a.) E [0, 1). 1 reward function is a function f X' x A + [0. I]: in particular, f" is the true reward function. The reward structure is given by a known class of reward functions which contains f"; the assumption I F is known as realizability. To recap, the problem instance is a pair (f² where F is known and f is not.
We focus on finite reward structures, i.e., assume (unless specified otherwise) that A, are all finite. While this does not hold for most reward structures from prior work, one can discretize them to ensure finiteness. Indeed, when reward functions can take infinitely many values, one could round each function value to the closest point in some finite subset S C [0, 1], e.g., all integer multiples of some E > 0. Likewise, one could discretize contexts, arms, or function parameters, when they are represented as points in some metric space, e.g., as real real-valued vectors. Or, one could define finite reward structures directly, with similar discretizations built-in (see Appendix D for examples).
We are interested in expected regret E R(t)) as function of round f. Regret is standard: R(t) == Exe(g (r*(x)) rr.). where r" (xx == m f (ax, a), best expected reward given context æ.
The greedy algorithm (Greedy) is defined follows. It is initialized with To 2 1 rounds of warm-up data, denoted E [To]. Each such round yields a context-arm pair (oz. ae) E X' x A chosen exogenously, and reward r, E E drawn independently from the resp. reward distribution: unit-variance Gaussian with mean (" at)- At each round t. > To. Greedy computes a reward function via least-squares regression (implemented via "regression oracle", per Section T):
ft argmin Eietg 0z) )²
(2.1)
Note that there are no ties in 2. with probability one over the random rewards. Once reward function ft is chosen, the algorithm chooses the best arm for fr and context T2, i.e.
at E argmax fe(
(2.2)
For ease of presentation, we posit that [(x,, has unique maximizer, for each feasible function f T F and each c E X'; call such ʃ best-arm-unique. (Our results can be adapted to allow for reward functions with multiple best arms, see Appendix(A)
Notation. Let K be the number of arms; identify the action set as A = [K]. The number of times given arm was chosen for a given context æ before round t is denoted N₂ (z, a), and the corresponding average reward is Fz( a). Average reward over the warm-up stage is denoted Fuarm (z, a) = Fz( a) with To + 1. We'll work with alternative loss function,
MSE, (f) = E (x.a)xxx Ne( a) ( (Fe(2, a) f(x,a))²
(2.3)
Note that it is equivalent to 2.. for minimization, in the sense that Sa argmin (S).
3 Characterization for structured bandits
Let us focus on the paradigmatic special case of multi-armed bandits, call it StructuredMAB Formally, there is only one context, | = 1. The context can be suppressed from the notation; e.g. reward functions map arms to [0, 1]. An arm is called optimal for given reward function f (or, by default, for f*) if it maximizes expected reward f-). and suboptimal otherwise.
We start with two key definitions. Self-identiffabiiiy (which drives the positive result) asserts that fixing the expected reward of any suboptimal arm identifies this arm suboptimal.
Definition 1 (Self-identife Seeffiddeniffiabiiitt).. Fix problem instance (f", A suboptimal arm is called self-identifiable if fixing its expected reward f (a) identifies this arm as suboptimal given F, i.c. if arm a is suboptimal for any reward function f E F consistent with f(a) = (a). If all suboptimal arms have this property, then the problem instance called self iif-identifiable.
4. Whether the context distribution is known to the algorithm is inconsequential, since Greedy (particularly, the regression in Eq. 22.1 does not use this knowledge. W.l.ogg.. X is the support set of the context distribution. Gaussian reward noise a standard assumption bandits (along with e.g., 0-1 rewards), which we make for ease of presentation. Our positive results carry over to rewards with an arbitrary sub-Gaussian noise, without any modifications. Likewise, our negative results carry over to rewards r, E [0. 1] with an arbitrary near-uniform distribution, iee. one specified by p.d.f. on [0, 1] which is bounded away from 0 by absolute constant. 6. We also refer to the first To rounds as warm-up stage, and the subsequent rounds main stage.

---

A decoy (whose existence drives the negative result) is another reward function faee such that its optimal arm Adec is suboptimal for f and both reward functions coincide on this arm.
Definition 2 (Decoy). Let f", Jaas be two reward functions, with resp. optimal arms a² adac- Call Jaec decoy for f (with decoy arm Odse) if it holds that (asc)) = = ("aoc) < <S* (a").
We emphasize that self- oeffiidentffiaiiittyy and decoys are new notions, not reducible to structural notions from prior work, see Appendix B It is easy to see that they are equivalent, in the following sense: Claim 1. An instance (f", F) self-identifiable if and only if f has no decoy in F.
In our characterization, the complexity of the problem instance Ff) enters via its function-gap
min T(f", functions JEF: $+1
min (1
(a) - f(a))-
(3.1)
amms
We may also write T(f*) [f" F)) when the function class F is clear from context.
Theorem 1. Fix problem instance FF) of StructuredMAB.
(a) If the problem instance is self-identiffuble, then Greedy (with any warm-up data) satisfies E [R(()] < To + (K/T( O(log 1) for euch round (. E N.
(b) Suppose the warm-up data consists of one sample for each arm. Assume f has a decoy Sanc F, with decoy arm Gasc. Then with some probability Pasc > 0 it holds that Greedy chooses Odec for all rounds i E (Tb,00), We can lower-bound Paac by e e-O(K/T9(aa)))
Discussion. Thus, Greedy succeeds, in the sense of achieving sublinear regret for any warm-up data, if and only if the problem instance is self-identifiable. Else, Greedy fails for some warm-up data, incurring linear expected regret. Specifically, regret is E [R(()] 2 (1-To) Paac (f* (a*) (Mase)
for each round t E (To. oo), where a" is the best arm.
The correct perspective is that Greedy fails on every problem instance unless self- cefffidentifiabilityy makes it intrinsically "casy". Indeed, consider any bandit algorithm that avoids playing an arm once is identified, with high confidence, suboptimal and having specific expected reward. This defines a mild yet fundamental non-degeneracy condition: a reasonable bandit algorithm should never take an action that provides neither new information (exploration) nor utility from existing information (exploitation), whether it prioritizes one or balances both. The class of algorithms satisfying this condition is broad-for instance, an algorithm may continue playing some arm a indefinitely as long as the reward structure permits this arm to be optimal. However, under self-identifiabiiity, any algorithm satisfying this condition achieves sublinear regret (see Appendix foor details).
The failure probability Paec could be quite low. When there are multiple decoys faec E F, we could pick one (in the analysis) which maximizes function-gar gap I(faac). We present more efficient analysis under stronger assumptions (which also applies to infinite function classes), see Section [
a).. We show that suboptimal arm cannot be chosen more than Ö(K/T² times throughout the main stage. Indeed, suppose is chosen this many times by some round f > To. Then Fr (a), the empirical mean reward for a, is within r/2 of its true mean (a with high probability, by standard concentration inequality. This uniquely identifies (a) by definition of the function-gap gap. which in turn identifies a as a suboptimal arm for any feasible reward function. Intuitively, this should imply that cannot be chosen again. Making this implication formal is non-trivial, requiring an additional argument invoking MSE, (-), as defined in (2.3)
Proof Sketch for Theorem
First, we show that (f* & Ō(K) with high probability, using concentration. Next, we observe that any reward function with f(a) + (a) will have a larger MSEx(-), and therefore cannot be chosen in round t. It follows that fa(a) = (a). Consequently, arm a is suboptimal for fi (by self-identifiabilityy.. and hence cannot be chosen in round
Proof Sketch for Theorem [b). To show that Greedy gets permanently trapped on the decoy arm despite reward randomness, we define two aanefully-construcc warm-up up data causes Greedy to misidentify fasc as the true reward function for all non-decoy arms:
events. The first ensures that the
E = { |oarn (a) - faoc(a) < T(faec/22 for each arm a o Gdec }.
(3.2)
5

---

This concerns the single warm-up sample per non non-decoy arm. The second event ensures that the empirical mean of the decoy arm dear remains close f (daae) for all rounds after the warm-up:
E2 {vt > To. [Fe(daee) - (aaec) ) S [f
(3.3)
Under Ei n E2, Greedy always chooses the decoy arm. To lower-bound Pr Ej n E2 note that E2, En are independent (as they concern, resp., Odac and all other arms), analyze each event separately.
4
Characterization for structured contextual bandits (StructuredCB)
The ideas from Section Iaationnnneee Ieed non-trivial modifications. The naive reduction to bandits treating each contexts-to-arme mapping as a "super-arm" " in StructuredMAB- does not work because Greedy now observes contexts. Further, such reduction would replace the dependence on K in Theorem I with the number of mappings, i.e., K KIX), whereas effectively replace it with K [x
mappings from contexts arms are commonly called policies. Let II denote the of all policies. Expected reward of policy π E II is (x) := E, (x, Tx))]] where the expectation over the fixed distribution of context arrivals. A policy
Some notation:
called optimal for reward function f it maximizes expected reward fT) and suboptimal otherwise. Let x be the optimal policy for f"
Note that т (xx) E argmax [(x .) for each context æ, which is unique by assumption..
Greedy can be described in terms of policies: it chooses policy Fy in each round 4, before seeing the context Tt, and then chooses dg = (xx)) Here n, is the optimal policy for the Se from Eq. 2.1p.
As in Section 3 the positive and negative results are driven by, resp.. self-identifiabiiitty and the existence of suitable "decoy". Let's extend these key definitions to contextual bandits.
Definition 3 (Self-identiffe identiiiaiiiiiitt. Fix a problem instance (F) A suboptimal policy π E I1 is called self-identifiabe if fixing its expected rewards f" (z)) for all contexts E X identifies this policy as suboptimal given F. Put differently: if this policy is suboptimal for any reward function f such that (())) f (æ, TTx)) for all contexts If each suboptimal policy has this property, then the problem instance is called self-identifiable.
Definition 4 (Decoy). Let f* faec be two reward functions, with resp. optimal policies '²", Teec- Call feee a decoy for f (with a decoy policy Tasc) if it holds that [Tec()Taec) =f" < f*²")) and moreover feec (z., (x)) fx, (x)) for all contexts X.
In words, the decoy and f completely coincide on the decoy policy, which a suboptimal policy for f The equivalence of these definitions holds word-by-we bord-by-word like in Claim [
The notion of function-gap gapiionnngpppp is extended in natural way:
((f,F)
min functions FFF
min (s,a)exxx: f(za)) (2,a)
ax) f(x, a))-
(4.1)
Our results are also parameterized by the distribution of context arrivals, particularly by the smallest arrival probability across all contexts, denoted po- (W.l.o.g.. Po > 0.) Theorem 2. Fix problem instance (f",F)
F) of StructuredCB. Let X = (2
(a) If the problem instance is selffiidentifiable, then Greedy (with any warm-up data) satisfies E [(()] < To + (IX)K/T((*)) )² /po O(log 1) for each round e N.
(b) Suppose the warm-up data consists of one sample for each context-arn pair. Assume f has a decoy faee E F, with decoy policy Taec. Then with some probability Paec > 0, Greedy chooses Taec in all rounds t (o), We have Paec 2 X X-O(KX/T" ((me))
Remark 1. Greedy succeeds (i.e., achieves sublinear regret for any warm-up data) if and only if the problem instance celffidentifiable Else, Greedy fails for some warm-up up data, with linear regret:
E [(R()) 2 (1 (1-Ta) To) Paac (J*(T") _- (TTTaa)) (iraaa))foo for each round E (To, oo).
(4.2)
New Proof Ideas. For Theorem 2a. directly applying the proof techniques from the MAB case gives a regret bound linear in |II KX_ Instead, we develop a non-trivial potential argument to achieve regret bound polynomial in K For Theorem{2t)) we give new definitions of events E,, Ez extending (3.2p. (3.3) by carefully accounting for contexts, and refine the deviation analysis to remove the dependence on [I]. Proof sketches and full proofs are in Appendix

---

5 Interactive decision-making with arbitrary feedback
We consider Decision-Making with Structured Observations (DMSO), general framework for sequen- tial decision-making with a known structure [Foster et al., 2021]. It allows for arbitrary feedback observed after each round, along with the reward | The root challenge is that this feedback usually correlated with rewards. Greedy must account for these correlations, not just compute the best fit based on rewards. Our solution is to develop a natural variant of Greedy based on maximum- likelihood estimation. The analysis then becomes much more technical compared to StructuredCK requiring us track changes in log-likelihood and define the "model-gap" in terms of KL-divergence.
Preliminaries. DMSO is defined as follows. Instead of "arms" and "contexts", we have two new primitives: policy set IT and observation set O. The interaction protocol is follows: in each round f = 2, the algorithm selects a policy Te E II, receives a reward rz E R C R. and observes an observation Or O. A model is a mapping from II distribution over R x O. The reward-observation pair (Fr, 0²) is an independent sample from distribution M (T+), where M is the true model. The problem structure is represented
(known) model class M which contains M We assume that II, M, R. O are all finite 8 To recap, the problem instance is a pair (M",M) where M is known but M is not. This completes the definition of DMSO.
StructuredMAB is a simple special case of DMSO with one possible observation. StructuredCB is subsumed by interpreting the observations o as contexts and defining (T) accordingly, to account for the distribution of context arrivals, the reward distribution, and the reward function [ The observations in DMSO can also include auxiliary feedback present in various bandit models studied in prior work. To wit: rewards of "atomic actions" in combinatorial semi-bandit, [e.g.. György
al. 2007 Chen et al. 2 , per-product sales in multi-product dynamic pricing [e.g.. Keskin
and Zeevi 2014 den Boer, [014], and rewards of all "adjacent" arms in bandits with graph-based feedback (Alon et al. 2013 2015]. Moreover, the observations can include MDP trajectories in episodic reinforcement learning [see Agarwal et al. 2020) for background). DMSO subsumes all these scenarios, under the "realizabilitty" assumption M M.
We use some notation. Let ((( be the expected reward for choosing policy π under model M, and (m) (+ A policy is called optimal (under model M) if it maximizes f(- IM), and suboptimal otherwise. Let n² be an optimal policy for M The history He at round f consists of
(Tx, Tsy o.) tuples for all rounds s < D D' denotes that distributions D, D' are equal.
Modified Greedy. The modified greedy algorithm (CreedyMLE) uses maximum-likelitood estimation (MLE) to analyze reward-observation correlations. As before, the algorithm is initialized with To 2 1 rounds of warm-up data, denoted & E [To]. Each round yields a tuple (Te, Tt. 0₂) E II x IR x O, where the policy ne is chosen exogenously, and the (rt, pair is drawn independently from the corresponding distribution M* (TT)). At each round / >> To. the algorithm determines
M, E argmaxMeM L(M He),
(5.1)
To the model with the highest likelihood L(M)H) given history He (with ties broken arbitrarily)
Then the algorithm chooses the optimal policy given this model: ne E argmax [ MM). For simplicity, we assume that the model class M guarantees no ties in this argmax. Here [MM)H is an algorihmm-independent notion of likelihood: the probability of seeing the reward-observation pairs in history He under model M, if the policies in He were chosen in the resp. rounds. In a formula,
[(M Ho) = [L PI (T,,, 0.).
(5.2)
W.l.o.g. we can restrict 11 to policies that are optimal for some model; in particular [1I] S (M).
Our characterization. We adapt the definitions of "self-identio "seff-identifiabiltty"" and "decoy" so that "two models coincide on a policy" means having the same distribution of reward-observation pairs.
Definition 5 Self-identiffabiiityy. Fix a problem instance self-identifiable if fixing distribution (x) identifies this policy as suboptimal given M. That is: if
A suboptimal policy n is called
Bandit formulations with partial feedback that does not include the reward [known as partial monitoring.
e.g., Bartók et al. 20144] Antos et al., 22013), are outside our scope.
8. Finiteness of R, T' for case of presentation. We can also handle infinite R, O if all outcome distributions
(ir have a well defineed density, and Assumption I is stated in terms of these densities.
9. Here we work with discrete rewards, whereas our treatment in Sections and
Gaussian rewards.
10. As in Section 2 the regression is implemented via "regression oracle" 7 tocus on statistical guarantees.
7

---

policy π is suboptimal for any model M M with M() E M (T). The problem instance is called self-identifiable if all suboptimal policies have this property.
Definition 6 (Decoy). Let M Maac be two models, with resp. optimal policies n², Taac- Call
Maec a decoy for M (with decoy policy aeee) if Maec(TTae)) 4 MM (Taee) (i.e., the two models completely coincide on Taee) and moreover π (TTec) < ff((") (i.e., Waec is suboptimal for f*).
Claim 2. DMSO instance (M) is selffideetif if and only if M has no decoy in M.
We define model-gap, a modification of function gap which tracks the difference in reward-observation distributions (expressed via KL.-divergence, denoted Drt.). The model gap of model M E . is
min M) == M'E.M, zell: (+))+(((+)
DEL ( (M(),, M (z)))
Our characterization needs an assumption on the ratios of probability masses:
Assumption The ratio Pr (r.o) Pran(s) (r, o) is upper-bounded by < co, for any models M, M' M, any policy π E 11, and any outcome (r, o) R O.
Theorem 3. Fix an instance (M) of DMSO with Assumption 1 and model-gap I' T-M", M.).
(a) the problem instance is self-identiiiable, then GreedyMLE (with any warm-up data) satisfies E [R(()] < To + (ITT In(B)/T)² O Inn (MM) t)) for each round t N.
(b) Suppose the warm-up data consists of No co (In(B)/T)2 log [M] samples for each policy, for an appropriately chosen absolute constant co (for the total of To = NoIII| samples). Assume M* has decoy Maac F, with decoy policy Taec- Then with some probability Pasc (No III) > 0, GreedyMLE chooses Tasc in all rounds E (To, oo).
GreedyMLE succeeds (i.e., achieves sublinear regret for any warm-up data) if and only if the problem instance is self-identifiable Else, it fails for some warm-up data, with linear regret like in Eq. (4.2). We also provide more efficient lower bound on Pasc in Theorem (b). replacing B with term that only concerns two relevant models, Masc; M (not all of M). Letting Doo be the Renyi divergence,
Pñac 2
OCacc IT) where Case maXTel D (Mace(T) MI S log B.
(5.3)
Proof Sketch for Theorem 3 We consider the likelihood of a particular model M E M given the history at round t 2 2, C. == L(M H4)) We track the per-round change in log-likelihood:
( = log L (M) - log La (M) log (P))(s)) (rt, 0t))
(5.4)
Let (.))) 1, so that 5.4) is also well-defined for round ( = 1.
We argue that the likelihood of M grows faster than that of any other model M M. Specifically, we focus on (x(M) = ([AA((M) - Af((M)). We claim that
N)
If (T,,)) d (T;)) then +x(M)= =0 else F,(M) 2 T.
(5.5)
In more detail: the two models completely coincide on policy Te, then (M = & and otherwise we invoke the definition of the model-gap. We use (5.5) for both parts of the theorem. The proof of Eq. (5.5) is where we directly analyze regression and invoke the model-gap.
Part (a). Suppose CreedyMLE chooses some suboptimal policy ne in some round /. > To of the main stage. By Eq. (5.5) and self-identifiabiiity, it follows that 4, (M,) r. (Indeed, by (5.5) the only
alternative is M (T,) = (TT)) and then self-iden iefffidentiiiaiiiity implics that policy is suboptimal for model Mc. contradiction.) Likewise, we obtain that (MM) 2 I for any model M e M for which policy ne is optimal; let Mape (T) be the set of all models for which policy æ is optimal.
We argue that suboptimal policies и E II cannot be chosen "too often". Indeed, fix one such policy æ. Then with high probability (w.h.p.) ) the likelihood of any model M E Mopp (T) falls below that of M so this model cannot be chosen again. So, w.h.p. this policy cannot be chosen again.
11. Related (but incomparable) assumptions on mass/density ratios are common in the literature on online/offline
RI., [e.g., Munos and Szepesvári 2008 Xie and Jiang 2021 Zhan et al. 2022 Amortila la et al. 2024
12. This last step takes union bound over the models MI Mope (T.. hence (JV) the regret bound.
8

---

Part (b). We define independent events E1 and E2, resp., on the warm-up process and on all rounds when the decoy is chosen, so that E, 7 Es guarantees that GreedyMLE gets forever stuck on the decoy. While this high-level plan is the same as before, its implementation is far more challenging.
To side-step some technicalities, separate out 2 warm-up rounds in which the decoy policy Tdec is chosen. Specifically, w.l.o.g. we posit that Tdec is chosen in the last No/2 2 warm-up rounds, and let Huarn Hrg+1, TV == To No/2 be the history of the rest of the warm-up.
First, consider the "ghost process" (ghost) for generating Hwarn: in each round I To. the chosen policy Te stays the same, but the outcome (Tt, 0c) is generated according to the decoy model Maec- Under ghost, each round raises the likelihood L (MMMe)) more compared to any other model M E M. Namely, write (M) = (M | H4) explicitly as a function of history He, and let
4,(M, Maac)= == E AM H4) - ( HH,)),
(5.6)
where H, comes from ghost. Reusing Eq. (.5 (with Masc now replacing true model M*), yields:
If Maac (T+) M( then p, Maac) = 0 else 4, Maac) 2 r.
(5.7)
For each model M E M different from Maec there is a policy π E II on which these two models differ. This policy appears No times in the warm-up data, so by Eq. (5.7) we have Eierra De(M, Maec) 2 r- No. Consequently, letting Mother := -M) M Maec }. event
E = ( E Mother [(Maec Hwarn) > C(M Hvara)
happens w.h.p. when Hoarn comes from ghost Since ghost and Hearn have bounded Renyi divergence, we argue that with some positive probability, event E₁ happens under Hwarn.
13
Let's analyze the rounds in which the decoy policy Teec is chosen. Let t(j) be the j-th such round, j E N. We'd like to argue that throughout all these rounds, the likelihood of the decoy model Ma grows faster than that of any other model M E M.M To this end, consider event
FB = [vj No/ VM E Mother: Every V. (M) 20),
where ; (M) Ae (Macc) Alu (M). Here, we restrict to > N ensure that F1, Fe concern disjoint sets of events, and hence are independent. Fg n Fby implies that in each round f. >>> To- (Mocc) > (M) for any model M E MMuster and so GreedyMLE chooses the decoy policy.
Finally, we argue that Eg happens with positive probability. W.L.o.g, the outcomes or) in all rounds t t(j), j N are drawn in advance from an "outcome tape") (4p (4 We leverage Eq. (5.5) once again. Indeed, 1,(M = 0 for every model M E .M that fully coincides with Maec on the decoy policy Taec. we only need to worry about the models M E M for which this is not the case. Then Eieni TE (M)) 2 j P. We obtain Σieb] E [M)] 2 0 with positive-constant probability by appropriately applying concentration separately for each > N and taking union bound.
Structured bandits with an Infinite Function Class
We obtain partial characterization for StructuredMAB, which handles arbitrary infinite function class F and yields better constants compared to Theorem [ The success of Greedy requires a stronger notion of self cofffddentifaabiiity: approximately fixing the expected reward of a suboptimal arm identifies it as suboptimal. The failure of Creedy requires a stronger notion of a decoy function, which must lie in the "interior" of F. The characterization is "partial" in the sense that it does not yield a full dichotomy. However, the boundary between success and failure is controlled by a tunable "margin" parameter
O, which can be made arbitrarily small (and optimized based on the instance).
Definition 7. A problem instance (f",F) is c-self-identtifable & 2 0, if any suboptimal arm a of f" is suboptimal for any reward function f E F with (f(a) - f*(a) S e. An e-interior of F, int(F,e) the set of all functions f F, such that any reward function f with I| f S é is also in F.
13. This argument invokes a concentration inequality, which in turn uses Assumption Likewise, Assumption is used for another application of concentration in the end of the proof sketch. 14. Its entries j N are drawn independently from M (Toce), and (rrG), o(g) is defined the j-entry.

---

For a "continuous" function class such as linear functions or Lipschitz functions, int(F,E) typically includes all but an (())-fratioon of F. The choice of the Eg norm the definition of e-interior not essential: any Ep norm suffices. We provide the main theorem below; see proof in Appendix H
Theorem 4. Fix a problem instance FF) of StructuredMAB with an infinite function class FF (but a finite action A). For any & > 0 (which can be optimized based on )*
(a) the problem instance is sself-iieenifiallee then Greedy (with any warm-up data) satisfies E [(t)] I To + (K/e)² Ollog 1) for each round E N.
(b) Suppose the warm-up data consists of one sample for each arm. Assume f has a decoy feac E iint(FFE), with decoy arm adac- Then with some probability Paac > 0 it holds that Greedy chooses Osec for all rounds t E (To. ).). We can lower-bound Paec by e- -O(K3
This result mirrors Theorem I with the function gap replaced by E, allowing for instance- deppedden optimization of ε and tighter bounds. The proof for part (a) carries over with simple modifications. In contrast, proving part (b) is considerably more subtle. In the infinite case, Greedy may not get stuck on a single reward function it could almost surely switch among infinitely many. The key insight is that such fluctuations need not impact the arm choice: even as the predictor Se changes, the greedy selection 0r may remain fixed. The proof exploits this decoupling, constructing events where the algorithm persistently selects a decoy arm, even as the greedy predictors continue to evolve.
challenges. An "if and only if" characterization for arbitrary infinite function classes very difficult. First, one can no longer rely on the function-gap being strictly positive, which is a cornerston of our analysis in the finite case. Second, Greedy's 's behavior can be highly unstable: the algorithm's 's predictor fa can fluctuate indefinitely within a continuous region of functions that are all similarly consistent with data yet induce very different greedy action choices. As a result, the intuitive logic of "getting stuck decoy and staying there forever" does not directly extend.
Discussion:
The partial characterization in Theorem 4 is our proposed route to address these challenges. The margin E serves a dual purpose: it stands for the now-absent function-gap, and allows to deal with the predictor's instability (by showing that ag can remain permanently fixed).
However, this is still insufficient for a complete characterization. For many natural function classes, our framework leaves a set of instances, typically of fraction OEE), uncharacterized. The boundary between success and failure instances in general infinite space be highly complex; success instances can be very close to failure instances, making a sharp separation difficult. Our e-interior notion is designed provide a robust buffer around this boundary, the cost of leaving instances within that buffer "undecided." A tight characterization in full generality would likely require a more fine-grained analysis exploiting additional structural properties of the function class F.
7 Conclusions
We study Greedy in structured bandits and characterize its asymptotic success vs failure in terms of a simple partial-idente cantialiieetifiability property of the problem structure. Our characterization holds for arbitrary finite structures and extends to bandits with contexts and/or auxiliary feedback. In particular, we find that Greedy succeeds only if the problem is intrinsically "easy" for any algorithm which satisfies a mild non-degeneracy condition. We also provide a partial characterization for StructuredMAR with infinite reward structures (and finite action sets).
Several examples, both positive and negative, instantiate our characterization for various well-studied reward structures. We find that failure tends to be a common case for bandits, whereas both failure and success are common for structured contextual bandits.
We identify three directions for further work. First, extend our characterization to infinite action sets and infinite function/model classes (ideally with a complete characterization, as discussed in Section 6.. Second, consider approximate greedy algorithms, stemming either from approximate regression or from human behaviorial biases. Such algorithms, representing myopic human behavior under behavioral biases, were studied in Banihashem al. [2023), but only for unstructured multi- armed bandits. Third, while our "asymptotic" perspective enables a general characterization, stronger regrel guarantees are desirable for particular reward structures (and are known for only a few).
10

---

References
Yasin Abbasi- Yadkori, Dávid Päl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In 25th Advances in Neural Information Processing Systems (NIPS), pages 2312-2320, 2011.
Naoki Abe, Alan W. Biermann, and Philip M. Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-293, 2003.
Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Learning From Reviews: The Selection Effect and the Speed of Learning. Econometrica, 2022. Working paper available since 2017.
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E. Schapire. Contextual bandit learning with predictable rewards. In 15th Intl. Conf. Artificial Intelligence and Statistics (AISTATS), pages 19-26, 2012.
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Miro Dudik, Luong Hoang, John Langford, Li- hong Li, Dan Melamed, Gal Oshri, Siddhartha Sen, and Aleksandrs Slivkins. Multiworld testing: A system for experimentation, learning, and decision-making 2016. A white pa- per, available
ds raw http///atteereeeeeeeeeeeeeeeeeee /images///////
MWT-Wh pdf
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Dan Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen, and Alex Slivkins. Making contextual decisions with low technical debt, 2017. Techical report at wwwpii.org//bbaa.
03966.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learn- ing: Theory and algorithms, 2020. Book draft, circulated since 2019. Available at https: http:///thhhrrboookkkoko g github.iii
Rajeev Agrawal. The continuum-annn bandit problem. SIAM J. Control and Optimization, 33(6):
1926-1951, 1995.
Noga Alon, Nicolò Cesa- Bianchi, Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. In 27th Advances in Neural Information Processing Systems (NIPS), pages 1610-1618, 2013.
Noga Alon, Nicolò (esacBiaachh, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In 28th Conf. on Learning Theory (COLT), pages 23-35, 2015.
Kareem Amin, Michael Keams, and Umar Syed. Bandits, query learning, and the haystack dimension. In 24th Conf. on Learning Theory (COLT), 2011.
Philip Amortila, Dylan Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforeement learning. arXiv preprint arXhv:2401.0968) 2024.
András Antos, Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Toward classification of finite partial-moniorinng games. Theor. Comput. Sci., 473:77-99, 2013.
Peter Auer. Using confidence bounds for exploiaatinn-exploration trade-offs. J. of Machine Learning Research (JMLR), 13397-422, 2002. Preliminary version in 4/ IEEE FOCS, 2000.
Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved Rates for the Stochastic Continuum- Armed Bandit Problem. In 20th Conf. on Learning Theory (COLT), pages 454-468, 2007.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. of Computer and System Sciences, 74(1):97-114 February 2008. Preliminary version in 36th ACM STOC, 2004.
Kiarash Banihashem, MohammadTaggh Hajiaghayi, Suho Shin, and Aleksandrs Slivkins. Bandit social learning: Exploration under myopic behavior, 2023. Working paper at https: /ors:///arxvv wwwg/oos/////ooooooooooo.ooo. 232.20222.2222..2 Preliminary version in NewrIPS 2023, titled "Bandit Social Learning under Myopic Behavior".

---

Gábor Bartók, Dean P. Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitor- ing - classification, regret bounds, and algorithms. Math. Oper. Res., 39(4):9779997, 2014.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 67(3):1329-1344) 2021. Working paper available arxiv. org since 2017.
Mohsen Bayati, Nima Hamidi, Ramesh Johari, and Khashayar Khosravi. Unreasonable effective- ness of greedy algorithms in multi-armed bandit with many arms. In 33rd Advances in Neural Information Processing Systems (NeurIPS), 2020.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. J. of Machine Learning Research (JMLR), 22:133:1-133:49 2021.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochas- tic Multi-armed Bandit Problems. Foundations and Trends in Machine Learning, 5(1): 1-122, 2012. Published with Now Publishers (Boston, MA, USA), Also available at https: / /arxivi... org/ abs/ /0044 5721.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvari. Online Optimization in X- Armed Bandits. J. of Machine Learning Research (JMLR), 12:1587-1627, 2011. Preliminary version in NIPS 2008.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimiza- tion. In 49th ACM Symp. Theory of Computing (STOC), pages 72-85. ACM, 2017.
Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Comput. Syst. Sci., 78(5):
1404-1422, 2012. Preliminary version in COLT 2009.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. 20th Intl. Conf. on Machine Learning (ICML), pages 151-159, 2013.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual Bandits with Linear Payoff Functions. In 14th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS), 2011.
Richard Combes, Stefan Magureanu, and Alexandre Proutière. Minimal exploration in structured stochastic bandits. In 30th Advances in Neural Information Processing Systems (NIPS), pages 1763-1771, 2017.
Varsha Dani, Thomas P. Hayes, and Sham Kakade. Stochastic Linear Optimization under Bandit Feedback. In 2/th Conf. Learning Theory (COLT), pages 355-366, 2008.
Rémy Degenne, Han Shao, and Wouter M. Koolen. Structure adaptive algorithms for stochastic bandits. In 37th Intl. Conf. on Machine Learning (ICML), volume 119, pages 2443-2452, 2020.
Arnoud V. den Boer. Dynamic pricing with multiple products and partially specified demand distribution. Mathematics of Operations Research, 39(3):663-888, 2014.
Arnoud V. den Boer and Bert Zwart. Simultaneously learning and optimizing using controlled variance pricing. Management Science, 60(3):770-783, 2014.
Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient. In 16th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 385-394, 2005.
Dylan J. Foster and Alexander Rakhlin. Beyond UCB: optimal and efficient contextual bandits with regression oracles. In 37th Intl. Conf. Machine Learning (ICML), 2020.
Dylan Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive decision making, 2023. wRw.ttps::///
Dylan J. Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire. Practical contextual bandits with regression oracles. In 35th Intl. Conf. on Machine Learning (ICML), pages 1534-1543, 2018
12

---

Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
Todd L Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws incon- trolled markov chains. SIAM journal on control and optimization, 35(3):115-743, 1997.
András György, Tamás Linder, Gábor Lugosi, and György Ottucsák. The on-line shortest path problem under partial monitoring. J. of Machine Learning Research (JMLR), 8:2369- 24009, 2007.
J. Michael Harrison, N. Bora Keskin, and Assaf Zeevi. Bayesian dynamic pricing policies: Learning and earning under binary prior distribution. Management Science, 58(3))570--88, 2012.
Baihe Huang, Kaixuan Huang. Sham M. Kakade, Jason D. Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient- based algorithms for non-concave bandit optimization. In 34th Advances in Neural Information Processing Systems (NeurIPS), pages 29101-2911 2021.
Matthieu Jedor, Jonathan Louëdec, and Vianney Perchet. Be greedy in multi-armes bandits, 2021.
Working paper, available on ht https: / aaaii.iivv...... www.wwwwwwwww../o//too/oa.aa.ara www./oo///////oooooooooo/ee 2101 01086.
Kwang-Sung Jun and Chicheng Zhang. Crush optimism with pessimism: Structured bandits beyond asymptotic optimality, In 33rd Advances in Neural Information Processing Systems (NeurIPS), 2020.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks stochastic bandits. Advances in neural information processing systems, 31, 2018.
Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems (NIPS), pages 2-31-2 2018.
N. Bora Keskin and Assaf Zeevi. On incomplete learning and certainty control. Oper. Res., 66(4):1 11133--1666 116,, 2018.
N. Bora Keskin and Assaf J. Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopa policies. Operations Research,
2014.
Scok-Jin Kim and Min-hwan Oh. Local anti-connenntration class: Logarithmic regret for greedy linear
contextual bandit. Advances in Neural Information Processing Systems, 37:71525-77592. 2024.
Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In /8th Advances in Neural Information Processing Systems (NIPS), 2004.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In 40th ACM Symp. on Theory of Computing (STOC), pages 681-690) 2008.
Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "wisdom of the crowd". J. of Political Economy, 122(5):988- 1012, 2014. Preliminary version ACM EC 2013.
T.L. Lai and Herbert Robbins. Iterated least squares in multiperiod control. Advances in Applied Mathematics, 3(1):50-73, 1982.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In 19th Inil. World Wide Web Conf. (WWW), 2010.
Tyler Lu, Dávid Pál, and Martin Pál. Showing Relevant Ads via Lipschitz Context Multi-Armed Bandits. In 14th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS), 2010.
H. Brendan McMahan and Avrim Blum. Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. In 17th Conf. on Learning Theory (COLT), pages 109- 2004.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
13

---

Bart P. G. Van Parys and Negin Golrezaci. Optimal learning for structured bandits. Management Science, 70(6):3951-3998, 2024.
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM J. on Computing (SICOMP), 52(2):487-52) 2023. Preliminary version at COLT 2018.
Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411,,-411110 2010.
Ohad Shamir. On the complexity bandit and derivative-free stochastic convex optimization. In 26th Conf. on Learning Theory (COLT), volume 30, pages 3-24, 2013.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operation Research, 1703):10041193) 2022.
Aleksandrs Slivkins. Contextual bandits with similarity information. J. of Machine Learning Research (JMLR), 15(1):2533-255 2568, 2014. Preliminary version in COLT 2011.
Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286 November 2019. Published with Now Publishers (Boston, MA, USA).
Also available at https:://// /aass///rrxiii //r/aaaxvvvorreee/eaa wwt. abs////////// / 904. 07272.
Aleksandrs Slivkins. Exploration and persuasion. In Federico Echenique, Nicole Immorlica, and Vijay Vazirani, editors, Online and Matching-Basd Based Market Design. Cambridge University Press, 2023. Also available at https: / wwwaa.ivvv..... org/ abs 2/////41...11111 17006....6.
Andrew J Wagenmaker and Dylan J Foster. Instance-opiimality in interactive decision making: Toward a non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory, pages 1322-1472. PMLR, 2023.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11 11404-11413, PMLR, 2021.
Qian Yu, Yining Wang, Baihe Huang, Qi Lei, and Jason D. Lee. Sample complexity for quadratic ban- dits: Hessian dependent bounds and optimal algorithms. In 36th Advances in Neural Information Processing Systems (NeurIPS), 2023.
Wenhao Zhan, Baihe Huang. Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and angle-policy concentrability, In Conference on Learning Theory, pages 2730-2775. PMLR, 2022.
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackelberg games with an omniscient follower. In 40th Intl. Conf. on Machine Learning (ICML), pages 42304 42316, 2023.
14

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable "[No] ", it is perfectly acceptable answer "[No] provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" "we were unable find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way. we acknowledge that the answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendíx. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
15

---

Justification: Our main result assumees finite function class and comes with possibly large constants. We discuss these limitations detail, and also partially address them in our second main result in Section 6
Throughout, we assume realizability- standard assumption in structured bandit problems that the true model lies within the model class. While this assumption may not hold exactly in practice, it is pervasive in the bandits literature and serves as a foundational premise for theoretical analysis. Accordingly, our results should be interpreted in the context of this widely adopted framework.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "LLimitttios" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The paper provide full set of assumptions and complete proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
16

---

Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not contain experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification: The paper does not contain experimental results, hence the question does not apply.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp) cc/
public/ quides/ Cooe/oodeesieeeee commissionss ssiooooicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https)
for more details.
17

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not contain experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This question does not pertain since the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2iggma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
18

---

Justification:
The paper does not contain experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:////eaarsss..c./ooollll//ia
inee?
Answer: [Yes]
Justification:
We confirm the research conform with the Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a theoretical paper on multi-armed bandits, focusing on foundational aspects of the field. We do not anticipate any direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
19

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This question does not apply the current submission.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This question does not apply the current submission.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppaperswithhooe com/ dat aset s has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This question does apply the current submission.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
20

---

14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicabble, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This question does not apply the current submission.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
This question does apply the current submission.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMss if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
wttpriips..ccccceeeeeeeeeeee 20255 LLM) for what should or should not be described.
Please refer L.M policy
21

---

TECHNICAL APPENDICES
Contents
A StructuredCB with tie-breaking
23
Novelty of self-identifiabiliyy
24
Sell-identifiaiiiity makes the problem easy
24
Examples
25
D.1 (Discretized) linear bandits
26
D.2
(Discretized) linear contextual bandits
26
D.3
(Discretized) Lipschitz Bandits
27
D.4
(Discretized) polynomial bandits
28
D.5 (Discretized) quadratic bandits
30
StructuredMAB characterization: Proof of Theorem]
30
StructuredMAB Success: Proof of Theorem
30
StructuredMAB Failure: Proof of T'heorem l(b)
31
StructuredCB characterization: Proof of Theorem
32
StructuredCB Success: Proof of Theorem a
33
F2
StructuredCB Failure: Proof of Theorem
35
DMSO characterization: Proof of Theorem
35
DMSO Success: Proof of Theorem 3(a)
36
G.2
DMSO Failure: Proof of Theorem
36
StructuredMAB with an Infinite Function Class: Proof of [hhheeem
38
H.I Success: Proof of Theorem
38
H.2 Failure: Proof of Theorem
38
22

---

A StructuredCB with tie-breaking
Let us outline how to adjust our definitions and results to account for ties in Eq. 2.2 We assume that the ties are broken at random, with some minimal probability go > 0 on every optimal arm (i.e., every arm in argmax fe(Te, More formally, Greedy breaks ties in Eq. (2.2) according to an independent draw from some distribution D, over the optimal arms with minimal probability at least yo- Subject to this assumption, the tie-breaking distributions D, can be arbitrary, both within given round and from one round to another.
The positive results (Definition R and Theorem a))) carry word-by-word, both the statements and the proofs. The negative results (Definition 4 and Theorem 2jb)) change slightly. Essentially, whenever we invoke the optimal arm for decoy fdec. we need to change this all optimal arms for faec.
Definition 8 (decoy). Let f be a reward functions, with optimal policy x². Another reward function function faec is called decoy for f if any optimal policy Raac for faec satisfies faac (Raee) =f"((aee) f"( and moreover faee (2. (x)) = f=' (x)c( ( for all contexts x E X.
The equivalence of self-identifiability and having a decoy holds as before, i.e., the statement of Claim D carries over word-by word-by-word Moreover, it is still the case that "self-identifiabiiity makes the problem easy": all of Appendix Soandixxcarme carries over as written.
Theorem 5 (negative). Fix a problem instance (f" F) StructuredCB. Suppose the warm-up data consists of one sample for each context-arm pair. Assume f" has a decoy faee E F. Let Ia is the set of all policies that optimal for faac. Then with some probability Paac 0, Greedy only chooses policies Te E Taae all rounds (To,00), We have Paez 2 X-OIXX/(((m))) where X |.
Under these modifications, Remark applics word-by-word. particular, existence of a decoy implies linear regret, where each round & with E llaec increases regret by
Proof of Theorem The proof of Theorem 2bb mostly carries over, with the following minor modifications. Let A dec (x) argmax, faec (v) be the set of optimal arms for the decoy faee for
given context æ. The two events E₁ and Eg (as originally defined eq. (F.I) and eq. (22) will be
modified to be invoked on all decoy context-ane anm pairs.
Ej [ a) (x, a)l < 22 for each x E X' and arm a & (i)
FB (1r, Taac (1)) (", Taac (x))) < [( for each X.aa a (x), and round / To }o}
Analyzing the probability for event E, still follows from Lemma 20 Analyzing the probabil- ity for event Eg follows from Lemma 21 but with the choice of will be chosen as a ((((aa))) //I(((/(()) and we still have Pr[Es] 2 0.9.
23

---

B Novelty of self-identiffability
We argue that self-identifaabiityy is a novel notion. Specifically, we compare it to (i) knowing the optimal value, and (ii) Graves-Lai coefficient being 0.
First, one could ask if self-identifiabiiityy is equivalent to knowing the value of the best arm. However, the former does not imply the latter. Consider the simple example F = {(3, 1). 1)). Both functions are self seff-identifiable in FF but clearly the optimal value differs.
Second, consider the Graves-Lai coefficient [Graves and Lai 1997 Wagenmaker and Foster 2023 Let us define it formally, for the sake of completeness. Consider DMSO, as defined in Section 5 with model class M. Let
(TT = f(TM f(T
be the suboptimality gap for model M and policy т, where ни is the optimal policy for M. Let Malt be the set of models that disagree with M on the optimal policy:
M = {M' E MMITM # kM²
Now, the Graves-Lai coefficient is defined as
M) = inf 'EER"
ATA((M AM E MM) mEm
nT DEL (M(T)))M(() 21
TEll
Intuitively, the Graves-Lai coefficient measures the "verification" cost of verifying whether a given function f (or given model M in the DMSO setting) is indeed the model. The Graves-Lai coefficient being 0 implies that the learner can ascertain that I or M is indeed the true model by simply executing the set of optimal policies II()") or [I(M").
Now, one could ask if self-iddetifiabiliityy is equivalent to GLC(M, M) = O. We observe that this is not the case: the two notions are incomparable. For counterexample, consider StructuredMAB with two arms and F = {(2, 1), (0.5, 1)). Problem instance f = (0.5, 1) is self-identifiable, since revealing the sub-optimal arm having reward 0.5 immediately rules out (2, 1) as being the true model. But the GLC > O, since to ascertain (0.5, 1) as being the true model one necessarily has to and experiment. On the other hand,
choose the 1tt but has GLC = O. In this example, Greedy succeeds when GLC > 0 (larger GLC suggests larger regret of the optimal algorithm in GLC-based theory) but fails when GLC = 0 (lower GLC suggests lower regret of the optimal algorithm in GLC-based theory)! Hence GLC does not capture the per-instance behavior of Greedy.
see /" = (2, 1) is not self-identifiable
However, GLC has some connection to our machinery. Namely, GLC(FF, ff 0 for some reward function f, then necessarily cannot be decoy for any other reward function f" That said, GLC(F, provides no information about whether f itself admits a decoy. We believe that GLC precisely characterizes the asymptotic performance of the optimal algorithm [Graves and Lai 1997] Wagenmaker and Foster 2003), whereas self-identifiabilit precisely captures the asymptotic behavior of Greedy generally suboptimal algorithm.
C Self-identifiability makes the problem easy
Our characterization raises a natural question: does the success of Greedy under self-identifiability stem from the algorithm itself, from self-identifaaiiliyy, both? Put differently, when Greedy succeeds, does it make any non-trivial effort toward its success?
Surprisingly, our characterization provides definitive negative answer: Greedy succeeds because self-identifiability makes the problem intrinsically "easy." We prove that whenever self-identifiability holds, any reasonable algorithm (satisfying mild non-degeneracy condition defined blow) also achieves sublinear regret. This, in a sense, reveals the "triviality" of the greedy algorithm: succeeds only when the problem is easy that any reasonable algorithm would succeed.
To formalize this, we must clarify what we mean by "reasonable algorithms." Clearly, we need to exclude certain degenerate cases, such static algorithms that pick a single arm forever, neither exploring nor exploiting information. We argue that a reasonable algorithm should least care about -whthhe through exploration, exploitation, or both. In other words, reasonable
24

---

algorithm should never select an action that serves neither any exploration purpose (i.e., bringing new information) nor any exploitation purpose (i.e.. utilizing existing information). This principle naturally leads to information-aware algorithms formally defined below.
We work in the setting of StructuredCB, and explain how to specialize it to StructuredMAB.
Definition 9. Consider some round t in StructuredCB. We say policy is 5-identified-and suboptimal if there exists a suitable concentration event which happens with probability 6, such that under the concentration event, its mean rewards (x, (x)) for each context x exactly identified given the current history, and moreover this identification reveals that the policy is suboptimal given the function class.
For StructuredMAB, this definition specializes to defining d-identified-ande and and--aaddd--dsa suboptimal arms. Definition 10. An algorithm for StructuredCB (resp., StructuredMAB) is called d-information- aware if at each round, does not choose any policy (resp., arm) that is 8 5-identified-an and -ae---addd---- sundddsbptimma..
Let us define the concentration events: EnAB for StructuredMAB and Ecs for StructuredCE:
EyAs [Fr((o) - (a)) & (Ni(a)
Va A,EAteN),
(C.1)
Eca =
- - < Br a)( and N₂(x, > ((N((=) with (x) Vx E X, E II, LEN).
(C.2)
where Be(n) =
2 log
10K XX] e.
and (x(r) is the number of times context & has been
34
observed before round f. Here, Po is the smallest context arrivial probability, like in Section 4 Note that Exan is just specialization of Ecs.
Theorem 6. Consider StructuredCB with time horizon T. Any 1/z-informatioo-awwarr algorithm ALG achieves sublinear regret E R(T)) under self-identifiabiiiyy.
Proof. Assume Egg holds. Fix any suboptimal policy æ. We show can only be chosen o(T) times.
By the definition of (-) in the event Eca, there must exists some parameter T" (f) o(T)), such that (x(T") < I(f"). Then, if the suboptimal policy π is executed above the threshold Q(T" po), we have (1 a) > T", and consequently for any context x,
(x)) - (z, (x))) < B(T') <T(f))
Then recall for any function f and context-arm pair (x,, a). we have either f(x, a) fx, a) or [f a) (x, 2 T(f*). This precisely means the policy ı becomes identified, and by self- identifiability. any information-ave -ware algorithm will not keep choosing æ. Hence, the total regret of the information-awal algorithm is at most OT" [T],, which is sublinear o(T).
D Examples
Let us instantiate our characterization for several well-studied reward structures from bandits literature. We consider linear, Lipschitz, and (one-dimensional) polynomial structures, for bandits as well as contextual bandits. All reward structures in this section are discretized to ensure finiteness, as required for our complete characterization in Sections[3jo) (While our partial characterization in Section handles infinite reward structures, secondary goal of this section is to illustrate how common infinite reward structures can be mcaningfully discretized so that the complete finite-structure results become directly applicable.) The discretization is consistent across different reward functions, in the sense that all functions take values in the same (discrete) set R, with [R] < [F] This prevents a trivial form of teff-idetifiabbiityy that could arise if each reward function f were discretized independently and inconsistently. resulting in some f (a) values being unique and making f relf-identifiable solely due to the discretization strategy specific to [5
15. For example, consider an instance (f* FF) being not self Saff-identifiable, with decoy faue E F satisfying f" (daae) = (aa.c) 0.5. Now, suppose we discretize ("(aa)) using discretization step 0.1 and discretize Sauc(aaue using discretization step 0.2. After this modification, f ("(aao)) and fanc (aaec) would no longer be equal, and self-idente elffiidetifiability could occur.
25

---

On a high level, we prove that decoys exist for "almost all" instances of all bandit structures that we consider (i.e. linear, Lipschitz, polynomial. and quadratic). Therefore, the common case in all these bandit problems is that Greedy fails.
For contextual bandits (CB), our findings are more nuanced. Linear CB satisfy identifiability when the context set is sufficiently diverse (which is consistent with prior work), but admit decoys (as a somewhat common case) when the context set is foo--dimensional.. In contrast, existence of decoys is the common case for Lipschitz CB. One interpretation is that self-identifiabiiiy requires both context diversity and a parametric reward structure which enables precise "global inferences" (i.e, inferences about arms that are far away from those that have been sampled).
In what follows. we present each structure in a self-contained way, interpreting it special case of our framework. Since our presentation focuses on best-arm-unique reward functions, our examples focused similarly (except those for Linear CB). Throughout, let [y, y'le be uniform discretization of the [y, vf] interval with step & > 0, namely: yle = {E. E [v.0'] n E NJ. Likewise, we define (y, 3/)) ) == { E (v. y/: n N).
D.1 (Discretized) linear bandits
Linear bandits is a well-studied variant of bandits [Auer 2002 Abe et al. 2003 Dani et al. 2008 Rusmevichientong and Tsitsiklis 2010 Formally, it is special case of StructuredMAB defined as follows. Arms are valuev vectors: A c Rd. where E N is the dimension. Reward functions given by fo(a) algorithm, so the function class is F = { fo : 0 E O }. The true reward function is f = fo- for some 8" E O. (Fixing θ we interpret H" as a "problem instance".)
f for all arms a, where 0 E θ Rd The parameter set θ is known the
Linear bandits, as traditionally defined, let be (continuously) infinite, e.g., a unit ba-bll,, and sometimes consider an infinite (namely, convex) action set. Here, we consider a "discretized" version, whereby both @ and A are finite. Specifically, O (1= \ {0) )" i..., all parameter vectors in [0, 1] with discretized non-zero coordinates. Action set A is an arbitrary finite subset of [-11,, 1jd containing the hypercube {11, 3". Note that each reward function fo. 0 e θ has a unique best arm dg = sign(f) (f) == siggn(f))
[d] E {-1
We prove that linear bandits has a decoy for "almost all" problem instances.
{0} Lemma 1. Consider linear bandits with dimension d 2 2. parameter set Q -= ([-1,, \03)
E E (0, 1/4), and an arbitrary finite action set A C [-1, 1] containing the hypercube { {-1, 1 Consider an instance 0" O such that |10* ||1 min [0:] 2 de. Then Or has decoy in θ.
Proof. Let j E [d] be a coordinate with the smallest 10)1. Choose arm Adec E 1-,111 with (Adec): (fg ) for all coordinates i * j. and flipping the sign for i = j. (Aaec)s = sign (7)) Note that (8" (adee) = ||0 1 - 2 min,e [4] |6. E [ds,d]. d].
Now, for any given a E Ide, dle and any sign vector e E {-1, there is 0 E θ such that |0|| = and its signs are aligned as (f) = v. Thus, there exists Asec O such that ||0sec]| 1 (8" Azec) and sign( (lace) adoc. Note that Odec is the best arm for Paoc. Moreover, (faec (dec) = ||0aec 1
(0" (aac))
|111 (0*(a"). So, Peoc is a decoy for 6*.
D.2 (Discretized) linear contextual bandits
Linear contextual bandits (CB) are studied since Li et al. 2010 Chu et al. 2011 Abbasi- Yadkori al. 2011). Formally, it is a special case of StructuredCB defined as follows. Each context is tuple = (I(a) E R² a E A) E X' C d where d E N is the dimension and X' is the context set. Reward functions are given by fa(2, a) æ(a) 0 for all context-arm pairs, where 0 E θ C Bd and is a known parameter set. While Linear CB are traditionally defined with (continuously) infinite θ and X, we need both to be finite.
16. We consider stochastic linear bandits. A more general model of adversarial linear bandits studied since Awerbuch and Kleinberg 2008), McMahan and Blum 20044, see Bubeck and Cesa- Besa-Bianchi 2012 Chapter 5] for survey.
17. For ease of exposition, we relax the requirement that expected rewards must lie in [0, 1].
26

---

Like in linear bandits, the function class is F for some 8* ④ which we interpret as a "problem instance".
fo A E ) The true reward function is f = fo-
Remark 2. For this subsection, we do not assume best-arm-uniqueness, and instead rely on the version of our characterization that allows lies in (2.2). see Appendix A
We show that ceff-identifiabiiity holds when the context set is sufficiently diverse. Essentially, we posit that per-arm contexts sr(a) take values in some finite subset Sa C Rd independently across arms, and each Sa spans IR;; no further assumptions are needed.
Lemma 2 (positive). Consider linear CB with degree d Z and an arbitrary finite parameter set @ Rd.. Suppose the context set is X -TaaAA Sa, where Sa C [_,, are finite "per-arm" context sets such that each S. spans Fd. Then self- eefffideniffabiiiity holds for all instances 6* ④.
Proof. Fix some policy For given context x, let v(x) =(x(x)) E R be the context vector pro- duced by this policy. Let's construct a set Xg C X of contexts such that v(2g) == <xx) : x E Xg h. the corresponding set of context vectors, spans Rd. Add vectors to X, one by one. Suppose cur- rently v(2) does not span Rt Then, for each arm E A, the per-arm context set S. is not contained in span(v(An) (x))): put differently, there exists a vector Pa E S. \ span(u(26)) E Rdd Let (x(a)= V/ Va E AA E be the corresponding context. It follows that v(x) & (X)n( Thus, adding x to the set Xo increases span(r( (x))). Repeat this process till v(X)) spans Rd.
Thus, fixing expected rewards of policy π for all contexts in Ng gives a linear system of the form
v(z) 0" a(x) Vx E No:
for some known numbers axx) and vectors v(x), x E Ng. Since these vectors span Rd this linear system completely determines d".
Remark 3. In particular, Lemma holds when the context set is (very) small perturbation of one particular context x. For a concrete formulation, let S(a) [I(a) + E : i [d] } for each arm a and any fixed e >> 0, where ex, i E [d] is the coordinate-i unit vecfor. This consistent with positive results for Greedy in Linear CB with smoothed contexts (Kannan et al. 2018 Bastani et al. 2022] Raghavan al. 2023), where "nature" adds variance-q- Gaussian noise each per-arm context vector. (Greedy achieves optimal regret rates which degrade as increases, c.g., E [[(T)] S Ö(VT/o).) We provide qualitative explanation for this phenomenon.
On the other hand, decoys may exist when the context set X' is degenerate. We consider X' = Iae S., like in Lemma 2 but now posit that the per-arm sets S, do not span Rd even jointly. We prove the existence of a decoy under some additional conditions.
Lemma (negative). Consider linear CB with parameter set θ = (-1, 1,1,11 1 for some degree d 2 and discretization step E (0, 1/2] with 1/2 E N. Suppose the context set is X IL. Sa, where Sn [-11 1]d are the "per-arm" context sets. Assume span(S), ....... SK-1) C Rd-1 and SK = ((0,0...., 0,1)} Then any instance 0* e with 07 1 and 11011, 2 has a decoy in O.
Proof. Consider vector Qsec E θ such that it coincides with 0* on the first d components, and (0aec)a = -1. We claim that Oeec is a decoy for 0*
To prove this claim, fix context x E X. Let a* Odec be some optimal arms for this context under #* and fsece respectively. Then Ode: E K - 1]. (This is because the expected reward z(a) 8* of arm greater than -1 when a E [K- 1], and exactly - when a K.) Similarly, we show that a* = K. It follows that x((aaa)) Odac = x((dee)) -0*, since Oacc and 0" coincide on the first K - coordinates, and the last coordinate of xr( (((aas))
Moreover x x((ase)) 0 < 1 = x(a"). 0 Putting this together, ar (Aaac) faec = x(adcc) 8" < x(a") 8", completing the proof.
D.3 (Discretized) Lipschitz Bandits
Lipschitz bandits a special case of StructuredMAB in which all reward functions / E F satisfy Lipschitz condition, [f(a) - s(a') < D(a, a') for any two arms a, a' E A and some known metric D on A. Introduced in Kleinberg et al. [2008] Bubeck et al. (201T), Lipschitz bandits have been studied extensively since then, see Slivkins 2019 Ch. 4.4] for a survey. The paradigmatic case is
27

---

continuum-arae armed bandits [Agrawal 1995 Kleinberg 2004 Auer et al. 2007]. where one has action set A C. [o, 1] and metric D(a, a²) L- a'I for some >
Lipschitz bandits, as traditionally defined, allow all reward functions that satisfy the Lipschitz condition, and hence require infinite function class F. To ensure finiteness, we impose a finite action set A and constrain the set of possible reward values to a discretized subset R = [0, 1]e. We allow all Lipschitz functions A + R. Further, we restrict the metric DD to take values in the same range R. We call this problem discretized Lipschitz bandits.
We show that "almost any" any best-anm-und uniquue reward function has best-arm-uniquee decoy.
Lemma 4. Consider discretized Lipschitz bandits, with range R = [0, 1le and metric 'D Let F be the set of all best-arn-unique Lipschitz reward functions A + R. Consider a function I E F such that O < [(a) < {((")) some arm Then J has a decoy Saec E F (with decoy arm a).
Proof. Define reward function faee by (a' = min ( 0, f(a) -((a, } for all arms a' E A. So, Saec takes values in R. and is Lipschitz w.r.t. D (since D satisfies triangle inequality); hence Sasc E F. Also, Sasc has a unique best arm a (since [aa >> O and the distance between any two distinct points positive). Note that fa) = f(a) < f(a") so fdec is a decoy.
This result extends seamlessly to Lipschitz contextual bandits (CB) [Lu et al. albeit with somewhat heavier notation. Formally, Lipschitz CB is a special case of StructuredCB which posits the Lipschitz condition for all context-arm pairs: for each reward function f E F,
2010 Slivkins 2014],
[f a) f(x', a')l < ((,,,a) (z',a') Vx, X, a,a' E,,
(D.1)
where D is some known metric on X' x A. As traditionally defined, Lipschitz CB allow all reward functions which satisfy (D.I). We define discretized Lipshitz CB same way as above: we posit finite X, A. restrict the range of the reward functions and the metric to range R = [0, 1le, and allow all functions f x best-arm-und reward function has best-arm-unique decoy.
which satisfy (DII). Again, we show that "almost any" any
Lemma 5. Consider discretized Lipschitz CB, with range R = [0, 1]e and metric D. Let F be the set of all rest-arm-unique Lipschitz reward functions X x A - R. Consider a best-arm-unique function f E F such that for some policy π we have O < f(I, x(x) < f(z π (z)) for each context x. Then has a best-arm tat--arm-unnee arr-uuiquu decoy faec F (with decoy policy TT).
Proof. Define reward function faec by faee(zz,a) a) min 0. f(z, xx)) D D ((z, T())), (I, a)) for all context-arm pairs (z, a). Like in the proof of Lemma 4 we see that faee takes values in R and is Lipschitz w.r.t. D, hence faee E F. And it has unique best arm x (Ir) for each context Finally,
fase (2, 7 (x)) = f(x (x)) < f(, x² (x)), so Saec is decoy.
D.4 (Discretized) polynomial bandits
Polynomial bandits (Huang et al. 202 Zhao et al. 2023 is bandit problem with real-valued arms and polynomial expected rewards We obtain negative result for "almost all" instances of polynomial bandits, and a similar-but-clent but-cleaner result for the special case of "quadratii bandits".
We define polynomial bandits as special case of StructuredMAR with action set A C and reward functions f are degree-p polynomials, for some degree p E N. Denote reward functions as f = fo- where 0- = (fo, ... 0p) E - is the parameter vector with O, A O, so that fe (a) = Σp 0g a for all arms a. The function set is J = fe 0 E θ); for some parameter set O Typically one allows continuously many actions and parameters, i.e., an infinite reward structure.
We consider discretized polynomial bandits, with finite A and θ The action space A = [0, 1/2/.- for some fixed discretization step & E (0, ) The parameter set Q needs to be discretized in more complex way, in order to guarantee that the function class contains a decoy. Namely,
1-1/9: ////:////a// 1/olaig) where
8(4) = -+1-9
o==
18. Huang et al. 2021 Zhao et al. 2023) considered a more general formulation of polynomial bandits, with multi cialtiddmmesional arms a E E. It was also one of the explicit special cases flagged in Parys and Golrezaei 22024]
28

---

We "bunch together" all polynomials with the same leading coefficient 6g. Specifically, denote
, { θ , = } and F,, foo O E G, }. for y 0.
We focus on reward functions fo such that
O = arg max fe is unique and fo(ag) of (mmax A, aEA
sup
fo(a);
call such fo well-shaped. In words, the "best feasible arm in A" is unique, and dominates any larger discretized arm 19 (We do not attemptt to characterize which polynomials are well-shaped.)
We prove that "almost any" well-shaped function fo E Fr, has well-shaped decoy in Fy, for any non-zero " in some (discretized) range 20 Here, "almost all" is in the sense that every non-leading coefficient of must bounded away from the boundary by 5e, namely: 6g E [- + 5e, 1/u 5e for all q # p. Let Grdd be the set of all such parameter vectors 0 O.. Moreover, consider such that the best arm satisfies 0g >> E.
Lemma 6. Consider discretized polynomial bandits, as defined above, for some degree p 2 2 and discretization step (0, 2,). Fix some non-zero " E [-/p,, g/ Then any well- shaped reward function fo E Fry with 0 E ②baa and up > s has a well-shaped decoy in Fxy
Proof. Fix one such function fo- Consider a function Seec IR - defined by
faec(a) = fa + E) (fe(ag) - ( - =)) Va E R. In the rest the proof we show that faec is a suitable decoy.
(D.2)
First, we observe that faec Sen. where Osec E gp++1 is given by (0ace)p = 0p:
(faac) Σ
8t0,
4g= (p= 11) and
i=
P
(Daac)o Σ 0i (Jola)) Solag e)).
Second, claim that Osoe E 2r Indeed, the above equations imply that all coefficients of Ieoc suitably discretized: (faec)y e(- (-00, o0) for all E they are suitably bounded; this is where we use O E @bdd, We argue this as follows:
.P }. It remains to show that
Since 18y1 S 1/g for 9 O..... and Σ 1/(1!) c a simple calculation shows that [(laec) - 0gl < 35 for each 9 E {p ,,..,,1 ,1).
Since 10,1 < 1/9 for all q = 0.. O..... P and E [0, 1/2). simple calculation shows that fa)a) is 2-Lipehitz on A, so (fo(at) fo(az c)] S 2e, and moreover ((dac)o Gol S
35 + 25 = 5c.
Claim proved.
Third, we prove that Saec is well-shaped and is decoy for fe- Indeed, Eq. D.2 and ag > combined with the well-shaped condition (1) ag = arg max fe being unique and (2) fo (at) < suPae A,o)) fo(a), imply that (1) dgec ag i.e., arg max (a) and (2) (a < supag(max A,so), faec(a), which means that faec satisfies the well-shaped condition. Moreover, we have
E A is the unique best arm under fasc.
faoc(a = fo(a)e)) < fo(ag)
where the equality holds by D.2 and the inequality holds by the uniqueness of ag-
19. Being well-shaped mild condition. sufficient condition is as follows: arg max (co. fo is unique lies in (0, 1/2j. Note that even arg max.eR fe is non-unique or falls outside (0, 3/2], it still possible that fo is well-shaped, since arg max fo is not necessarily (-oc, 20).. 20. As a corollary. if we consider the function set consisting of all "well-shaped reward functions in F,"", then "almost any" function in this function set has decoy in the same function set.
29

---

D.5 (Discretized) quadratic bandits
Quadratic bandits is special case of polynomial bandits, as defined in Appendix D.4 with degree 2. Quadratic bandits (in a more general formulation, with culti-dimennionall arms a E RR) have been studied, as an explicit model, in Shamir (2013), Huang et al. (202T), Yu al. (2023). We obtain similar negative guarantee we do for polynomial bandits "almost any" problem instance has decoy but a cleaner formulation and a simpler proof.
Let's use more concrete notation: reward functions are fra.c with
f(r 7(a - -²²² + c,
where the leading coefficient y < 0 determines the shape (curvature) of the function and the other two parameters μr, c E [0. 1] determine the location of the unique global maximum (i.e., (p. c)).
Discretization is similar, but slightly different. The action space is A = [0, I]c, for some fixed discretization step & E (0, 1/2]- The parameter space θ i.e., the of feasible (7, 14, c) tuples, is defined as E [-1, 00.5 E [0. 1]e and c E (0, 1]a3. Note that js E A, so any function f(sa..)
has unique optimizer
1a A.
We focus on function space F, := { fGrue)) : (7, c) E }. grouping together all functions with the same leading coefficient y. We prove that "almost any" function in Fry has decoy in Fyy
Lemma 7. Consider discretized quadratic bandits, for some fixed discretization step & E (0, 1/2), Fix any leading coefficient Y [-1, - Then for any reward function f f(yai,) Fr. has decoy Jesc E Fry as long as μu, c are bounded away from p 2 e and e: 2 17|6"
Proof. Consider reward function faec - [(G, μ-e, e4ne2). Since p 2 s and c 2 17|e", follows that Jaac E Fy. Let us prove that Saac is a decoy for f Note that μ is suboptimal action for f and is the optimal action for Saec- Finally, it is easy to check that (" E) 7e² + Saee (1+ e). n
E StructuredMAB characterization: Proof of Theorem 1
E.1 StructuredMAB Success: Proof of Theorem (a)
Let us fix the time horizon and show the bound the expected regret [[[(t)]. Recall that Fa(a) as the empirical mean for arm a and that NN(a) is the number of times arm a pulled up to round t. Also recall the greedy algorithm is minimizing the following loss function each round:
MSE:(f) = Σ N((a)(F(a)- f(a))
&E[K]
Lemma 8. Define 3(n) V 2 log
x² 2
With probability 1- 8:
38
Va, r, (a) fa) < (NN)
Proof. This lemma is a standard Hoeffding plus union bound, this exact form has appeared in Jun al. 2018
In the following shall always assume the event in the previous lemma holds and choose 8 = 1/t. Lemma 9, Assume the event in Lemma then we have the upper bound on MSE, for each round [t].
MSE, (1*) S K O(log!). 1)-
Proof. Note that under the event from the previous lemma, we have for each arm:
(a( - f(a))² S (a) (
< <(logg 1).
Then, summing over all arms completes the proof.
30

---

Lemma 10. Assume the event in Lemma 8
The number of times any suboptimal arm is chosen cannot exceed T" rounds, where T some parameter with T (K/T(ff))) Oloo
Proof. We prove this by contradiction. Consider any round т during which some suboptimal arm a chosen above this threshold T'. The reward for arm is going to get concentrated within ((T()*)
to f (a), in particular:
[Fr(a) - <
Take any reward vector such that f'(a) * f(a). By the definition of class-gap, we have:
- ff =f(f".
hence
(--( (a)) P(/)2.
Then the cumulative loss
MSE, (f) 2 T (T(F*)/2)² K - 2(log
Therefore any I' with (a) o M(a) cannot possibly be minimizing (-). That to say, the reward vector f, minimizing MSE, (-) must have fo (a) = (a). Then, by self-iddetifiabiiitt, we precisely know that arm a is also a suboptimal arm for the reward vector fy. Hence, we obtain contradiction, and arm a cannot possibly be chosen this round.
We complete the proof of Theorem T[a as follows. The regret incurred during the warmup data is at most To- Fix any round & > To. After the warmup data, we know with probability 1/t, any suboptimal arm can be pulled most ()) Ollog t) times after the warmup data, and the regret is (K) (logt). With the remaining probability 1/t, the regret is at most Ot). Hence, the theorem follows.
E.2 StructuredMAB Failure: Proof of Theorem Ib)
Recall the events defined as
Ej { Fuarn (a) (a)) I(feec//2 for each arm + adec }
Es = 441 To, [Fe(Uaec) - I (adec)) S (/
Lemma 11. Assume event E₁ and Eg holds, then greedy algorithm only choose the decoy arm daec-
Proof. The proof is by induction. Assume by round f, the algorithm have only choose the decoy arm adec: Note that assuming event Ej and Eig holds, for any reward vector f # faec. we will have
(F((a) [aac(a)] S (a) s(a)),
with at least one inequality strict for one arm. Hence faec must (still) be the MSE, (-) minimizer, and Gdoc will be chosen in the next round.
[(fue)
exp(-2/02))
K-1 K-1
Lemma 12. Event Ej happens with probability at least
V2ra²
Proof. The random variable Fvara (a) is gaussian variable with mean (a) and variance σ², has a distribution density at with the following form
V2TT2 exp (f))=
For any æ in the interval [Saac (a) - ([[aac))/2 22, Jaac(a) + +((aaac) by boundedness of mean reward, have
x f (a)l < 2.
31

---

Then, the density of z at any point on the interval (a) least
[(faec/ faec(a) + (faec)/2) is at
exp exp(-2/o²).
V2TO2
Therefore, for any arm a, we have the following.
((Jac)
Pr[[Faam [a) S [(fass)/2]
exp(- exp(-2/o²).
2
Since the arms are independent, it follows that event Ej happens with probability
T(facc
K-1
V2Ta2 exp(-2/00)
Lemma 13. For some appropriately chosen o @(I(faoc)), we have event Eg happens with probability at least
Pr(E2) 2 0.9.
Proof. Denote the bad event
Eg = (31 To, F. - [aac(uaac)) > T(faac)/2).
which is the complement of E2. We will obtain upper bound on E3, therefore lower bound on Eg. Note that event Eg (and Eş) is only about the decoy arm Odecs and recall that ( (asec) = fdee (Adec).
By union bound,
Pr|Ea] <
Pr[li: - feee (Adec)l > I/2
t=1
< 2 exp( -t1 (faoc)
< 2exp (eex(_)(Jaac)) / /////////////)))))) )/1 -xxp(-T(facc))//
Here, the second inequality is by standard Hoeffding bound, and the last inequality is by noting that we are summing a geometric sequence.
Then, we can choose some suitable with o = ((T(fa)c) ensures Pr[Es] < 0.1 and that Pr[E2] > 0.9.
Lemma 14. For some appropriately chosen a = ((e(ee))) we have the following lower bound:
K-1
Pr E1
Eg]
Proof. Note that event E, and Eg are independent, then, the probability of Ej O Ez can be obtained from the previous two lemmas.
Theorem bbb directly follows from the above lemmas.
F StructuredCB characterization: Proof of Theorem 2
We start with a proof sketch, and proceed with full proofs.
Part (a). Directly applying the proof technique from the MAB case results in regret bound that linear in III apx Instead, we apply a potential argument and achieve regret bound that is polynomial in KX. First, by standard concentration inequality, f" as MSE, < Ō(KX) with high probability. Then, we use self-identifiabiiityy to argue that if in some round of the main stage some suboptimal policy π is chosen, there must exist some context-arm pair (z. (Ir)) that is "under-exploredd: appeared less than O(XK/T² times. This step carefully harnesses the structure of the contextual bandit problem. Finally, we introduce well-designed potential function (see Lemma [8 that tracks the progress of learning over time. This
upper-bound the loss for
32

---

function increases whenever suboptimal policy is executed on an under-explored context-action pair, allowing us to bound the total number of times any suboptimal policy is executed. A key challenge is that while the second step guarantees the existence of an "under-explored" context-arm pair, it does not ensure that the context actually appears when the associated policy is chosen. We address this using a supermartingale argument and the fact that each context arrives with probability at least Po in each round. Combining these steps, we upper-bound the expected number of times Greedy selects a suboptimal policy, and we bound the final expected regret via the regret decomposition lemma.
Part (b). As in the MAB case, we define event E1 ensure that the warm-up data misidentifies feec as the true reward function, and event Ey that the empirical rewards of the decoy policy are tightly concentrated. The definitions are modified to account for contexts:
E1 { Furrn f a)l 1 for each æ E X and arm + +T()) } E2 = {
(F.I)
(x)x < <((t)//2 for each x E X and round f > To } (F.2)
A decoy context-arm pair (zz, a) is one with = deec Ej concerns the single warm-up sample for each non-decoy context-arm pair. E2 asserts that the empirical rewards are concentrated for all decoy context-arm pairs (and all rounds throughout the main stage). The two events are independent, as they concern non-overlapping sets of context-arm pairs. Greedy always chooses the decoy arm when Ei, E2 happen. To lower-bound Pr E n E2 J. invoke independence, analyze each event separately.
F.1 StructuredCB Success: Proof of Theorem 2[a)
Recall (x, a) as the number of times that context x appears and arm a was chosen up until round t. Also recall the greedy algorithm is finding the function f that minimize the following function each round: MSE, (ff >nra (r, (F, a) - f(z a))².
Let us fix any E N. We will show the upper bound on the expected regret as stated in the theorem.
Lemma 15. Fix any 8 E (0, 1). Let (m) = / / log
=²XKn"
Then with probability at least 1 - 6,
36
Va, a s, |F, (x, - f(z, a)l s ((N.(z.))).
Proof. The proof is similar to that of Lemma 8 in the previous section, which is a Hoeffding-style concentration bound with a union bound. We can simply treat each context-arm pair (x, a) as an arm, and this directly yields the result.
In the following, shall assume the event in the previous lemma holds, and choose d 1/t. Lemma 16. Assume the event in Lemmal 15 holds. For any round E [t], the cumulative loss at the true underlying function, (f can be upper bounded as | O(logt) t).
Proof. We observe that
MSE. (f*)
Σ N,(r,a)FF((E,a)- f(z
Σ (0lo(((x])0)
3aa
< K O(log((*|]t)).
Lemma 17. Assume the event in Lemma 15 holds. Fix any round Te be some suitably chosen parameter and T" | ( O policy n in round Then there exists context such that (x)))(()) T'
X Kt)). Suppose Greedy executes some suboptinal
Proof. We prove this by contradiction. Suppose that suboptimal policy executed at round s, and further suppose that for all context x, we have N2(2, (()) 2 T".
By the previous lemma, we have Vz,
Fe(x, f (2, 8(T)) 1/2
33

---

Consider any function f such that:
Er +
+
(F:3
By the definition of the class gap,
and then
2
Then, the term MS) can be lower bounded:
(S) 2 T (T(()))))) | 0(log((x((())
Hence, any function satisfying Eq- F.3) cannot possibly minimize MSE,())- In other words, the function minimizing the loss at this step Je must satisfy
=
Finally, the self-identifiabiliyy condition precisely tells us the policy x must be suboptimal for fü and hence cannot be executed at round We obtain a contradiction, and the lemma is proven.
Lemma 18. Conditional on the event in Lemma 15 policy execution is no larger than [X KTT Po (X K/T(")))) O(log t).
the expected total number of times of suboptimal
Proof. Define the potential function as
M, = Σ min min (N,
2,0
Consider any round that a suboptimal policy π is executed, by the previous lemma, there exists a context arm pair (Ir, n (2:) such that (2, (xx) < T". With probability least po, such context x will arrive, and M, will increase by 1. Therefore, whenever suboptimal policy is executed, with probability least Po. will have M,+1 M, + 1.
Let us use the indicator variable La to denote whether a suboptimal policy is executed in round s. Then M, forms a supermartingale:
M 2 M,-1 + Po
Since we have that deterministically M, |KTTT, we know that the total number of times of suboptimal policy execution N, Σ.= satisfies
E
N.
E
< E
(E[M, Ms-1] M,-1))/po KT / /po-
Hence, the total number suboptimal policies pull is upper bounded as desired.
Proof of Theorem a). The regret incurred in the warmup phase is at most To- With probability 1 1/1, the number of suboptimal policy pulls be bounded in the lemma above. With the remaining 1/t probability the regret is at most Ott). Finally, by the regret decomposition lemma (Lemma 4.5 in Lattimore and Szepesvári 20200) ). we have
E[R(t)] < To + |X /Po + O(1)
To + (/T())))))) /po Olog
34

---

F.2 StructuredCB Failure: Proof of Theorem220 b)
Recall the two events
E1 = { Fuarm (x, a) - Seeo (z, a)l < 1( for each X and arm a * (T)c
E2 = { (1, (x)) f (z, (z))) < T(fass)2 for each E X and round & To
Lemma 19. Assume event Ei and E2 holds. Then the greedy algorithm only executes the decoy policy deec-
Proof. We prove this by induction. Assume up until round / the greedy algorithm only executes Wdec. Consider any other function f * Saec. Then we must have
Va, a (z a) f(x a)l 2 (Fe a) -socc
(aoc a))
And the inequality is strict for least one (x, a) pair. Hence faee is (still) the reward function minimizing MSE in round and the policy Maac will be executed.
L
Lemma 20. Event Ej happens with probability at least 92( [(fan) expl 2/0²) ||
Proof. The proof is similar to the counterpart in multi-arm bandits. Note that Fsarm (Ir, a) is gaussian distributed with variance o², We can obtain a lower bound by directly examining the distribution density of gaussian.
Lemma 21. For suitable chosen ((T /I(X)) event Eg happens with probability 0.9.
Proof. Similar the proof for multi-arm bandits, define the event
Eg E3t, x, |r, (z, (x)) faec (2, Taoe (x)) 2 [(fdec//2)
which is the complement of event Eg. By union bound,
Pr[Aa] = | Σ exp (-1 (Faec)/o))
t=1
$ X exp - T (facc)/ (acllllccpp(T(ecee/////
Choosing suitable O(T / ensures Pr[Es] 0.1, and consequently Pr Egg 0.9.
Lemma 22. We have the following lower bound:
Pr(E, n 2 log(I><)) [x exp(-2(log (x1)) (faac)((fanc)) 121k
Proof. Note that event Ej and Fg are independent, hence the lemma follows by the previous two lemmas.
Theorem b) now follows from the above lemmas.
G DMSD characterization: Proof of Theorem
Recall that (6,(M) is the change in log-likelihood for model M in round f, per 5.4) Note that
(M) AG((M') log (PrM(F)) (re, 0.) PTM((K) o:) E [- log B, log B].
The equality by (.4). and the inequality is by Assumption (and this how this assumption invoked in our analysis). We use the notation do log [ in what follows.
35

---

G.1 DMSO Success: Proof of Theorem 3|a)
The below lemma bounds the number of times any suboptimal policy can be executed.
Lemma 23. Let xt be any suboptimal policy. Fix ó E (0, D With probability at least - |M16, the policy x be executed for most O ( r r- lm(1/6)) rounds.
Proof. Let (TT)) be the class of models whose optimal policy is π². We show that after π² has been executed for T" rounds, any model in M (T²) cannot be the MLE maximizer with probability 1 MM Let Y₁ (M) be the difference in increase in log-likelihood of M and M in the 1-th round:
(M) = (4,))) (
Note that (M(M) is random variable where randomness comes from random realizations of reward- outcome pairs. (M) can exhibit two types of behaviors:
(M) corresponding to the case where M(T.) d (Tre (Lee, models M and M coincide under .Ty)
2. (M) is random sub-gaussian variable with variance S oj and that B[ 2T.
Consider rounds during which the policy x" is executed. Since x² is suboptimal policy, during these rounds, we know that (MM) is of the second type for any MM in (M") That is to say, is subgaussian random variable with variance upper bounded by O(og). ). and that further
E[Y((M)) = DKL (+T" (T)), MM (T)))
Since we have assumed T is suboptimal for the true model M we know that, E[Y[(M)] r.
Let Z((M) = Ei= Y²(M).
Pr[N)((7)) > T $ Pr/3s, E M² s.t. Z.(M(T)) S (=), = T
< |M1
Here in the last line we choose T" (of r-2 In ln(1/))) completing the proof.
We complete the proof as follows. By union bound, with probability |M [ the total number of rounds all suboptimal policy can be chosen is upper bounded by
0 M of r-2 In(1/)).
Choose d M|) and that log(1/8) O(Li)), then with probability 1 - 1/t, the total number of suboptimal policies executions can be upper bounded by
M
O(log([IIt)..
r
G.2 DMSO Failure: Proof of Theorem 3(b
In the subsequent discussion, we define Q(E) as the probability some event occurring under the assumption that the data is generated by the decoy model Maac (a hypothetical or ghost process). Similarly, we denote P(E) as the probability event occurring under the assumption that the data is generated by M (the true process).
Recall that the two events are defined follows.
E1 VVM& E Mother L(Maec Hwarn)
L(M Huaza))
and the event
== { Vj > No/2, VM E Mother: Eieny V. 2 0].
Where defined (M) = Alug) (Macc) (M)
We first begin with the following concentration result. This result is stated general manner and not specific to problem.
36

---

Lemma 24. Let X1,X2,... be sequence of random variables with X > I, and each is subgaussian with variance o². Then there exists some T" with T ( T22,, such that with probability - 8, for any 1. > T O(log 1/6),
Σx,0 X,>0
Proof. This lemma is by a standard concentration with union bound. We perform the following bounds
Pr
ビ T
Σ X,
Pr
Σ X3
0
t=
1=1
Σ exp(-lo (102/133)
l=
$ 8.
Here the last line by choosing a suitable 7" (0(02/13) and noticing we summing geometric sequence.
The below lemmas lower bound the probability that the likelihood of Maec will be the unique highest after the warmup data (assuming under ghost process Q).
Lemma 25. We have lower bound on Eς under the ghost process:
Q 2 0.9.
Proof. Fix model M F Maec- There must exist least policy that discriminates M and Maec in other words the distribution M and Maec (T) are different. Then, the expected change in oog-likeihooo of Masc is least I (Maac) greater than that of M for each time sample policy is observed:
P, Maec) Z r.
where we defined (M,, Maas) as per Eq. (.6
(M, Maac) == E ( Hc) A M H.)).
Moreover, we know that in each round, either (M Masc) or 4, (,M,, Maec) subgaussian random variable with mean greater than I' Further, during rounds when π is sampled, the latter will happen. The policy ı is sampled for N₂ co (oo/T'²² (o]((L))) times in the warmup phase. Then, by standard concentration inequality
Pr[fwarn (Macc) Evarn (M) < 0] < 0.1/IM).
Now, we take union bound over all models [M], and we obtain a lower bound for event Ej.
What remains is the to show a lower bound for the event Eg. We do so in the below lemma.
Lemma 26. Event Eg happens with probability at least 0.9.
Note that event Fg is only about when Maac is sampled. Since Maee (Taoc) M (TTdc), the ghost. process coincides with the true process.
Proof. Fix some model M. If the distribution for M(Trec) and Maac(Tasc) were the same, then V would be for any j. Hence we can assume (Faac) and Maee (Taac) different distributions. Then V would be a subgaussian random variable with IE(V, > I'Maae). By the previous Lemma 24, the event E3 holds specifically for model M with probability least 6/|M). Then, by union bound, event En holds with probability 8.
Lemma 27. If event E₁ and event Eg holds, then only mase is executed.
37

---

Proof. The proof is by induction. Clearly after the warmup phase, the policy Tdec is executed. Now suppose up until round t the policy ddac executed, by event Ez, the model Maac remains the log-likelihood maximizer, and hence Adac will still be chosen next round.
Proof of Theorem Bb) Now let P be the true underlying process for which data is actually generated according to true model M*. Recall Doo (Masc [M* S log B. Then the warmup data consisting of No samples, the density ratio the ghost process and true process is bounded by BlI|No, Therefore, the probability of event E can be bounded as follows.
P(EI) 2 Q(Ei)/B No
And after warmup GreedyMLE only choose Vdac by event E2. Hence, the final probability lower bound of always choosing deec after the warmup is Q
(2(B-11))) (B No).
H
StructuredMAB with an Infinite Function Class: Proof of Theorem
H.1 Success: Proof of Theorem (a)
The proof of Theorem a carries over with a modified version of Lemma 10 Thus, it suffices to state and prove this modified lemma.
Lemma 28. Let F be infinite function class. Assume the event in Lemma The number of times any suboptimal arm is chosen cannot exceed rounds, where is some parameter with T (K/e2)- Olog t).
Proof. We prove this by contradiction. Consider any round T during which some suboptimal arm a chosen above this threshold T'. The reward for is going get concentrated within (ss) to f (a), in particular:
(a+(a) (a)) <//2.
Take any reward vector f such that If(a') - f(a)] > Then we have
[Fr(a) - f(a)) 2 e/2.
Then the cumulative loss
MSE, (f') T (E/2)² K ()lo
Therefore any f' with (a) - f(a)) 2 cannot possibly minimizing MSE, (.). That is to say, the reward vector f. minimizing (-) must have (a) f (a)l E. Then, by the strong notion of e-self-identiffabiiiyy we precisely know that arm a is also a suboptimal arm for the reward vector fr- Hence, we obtain contradiction, and arm cannot possibly be chosen this round.
L
H.2 Failure: Proof of Theorem 4
The proof of Theorem (b) follows the same structure as Theorem [b) (see Appendix E.2
with key modification: although we still aim to show that Greedy becomes permanently stuck daec with constant probability, the regression oracle may no longer return faec exactly-its output may fluctuate around faee due to reward noise and the continuity of F. Our key insight is that, under suitable probabilistic events, these fluctuations do not change the greedy decision: the regression output may differ slightly from faec, but the resulting action remains adec-
Let us define the following events:
E1
Fvara( (a) (faoc(a) - =/(2/K)) <</(AVK) for each arm + adec f
Eg Vt To: (a((a)))) fr (asec)) <</(AVK)]
These events mirror 3.2 and 3.3 but with two changes: (1) we replace the confidence radius T(faac)/2 by e/(4/K) and (2) shift the baseline value of faoc(a) by (2/(2 in E.. We begin with three probabilistic lemmas.
38

---

- 22/2n0=R cxp(-2/o3) k-1
Lemma 29. Event E1 happens with probability least
Proof. The random variable (warn( (a) is a gaussian variable with mean (*(a) and variance a². has distribution density with the following form
V (xpp--xx- (
-
For any in the interval [Seac (a) reward, we have
(aac(()) 3e/(4v Jacc - e by boundedness of mean
x f-)a 22
Then, the density of a at any point on the interval (Saec(a) -3)((4/R), E/(4v is at least
exp( cxp(-2/o0).
V2T22
Therefore, for any arm we have the following.
Pr Fuarn (a) (a) - =/(22)) <</(AVK))
exp( exp (-2/0²). 2Too2K
Since the arms are independent, it follows that event E₁ happens with probability
K-1
2To=" K E cxp( cxp(-2/o²)
Lemma 30. For some appropriately chosen o = O(E/VK), we have event Eg happens with probability least
Pr(E2} 2 0.9.
Proof. Denote the had event
Eg = 3t To. Fr - faec( > e/(4v))
which is the complement of Ez. We will obtain an upper bound on Es, therefore a lower bound on Ez. Note that event Eg (and E3) only about the decoy arm adecs and recall that f (aaec) (Asec) by the definition of decoy.
By union bound,
T Pr[Es]
<
Pr i. /aoc(asec))) =/(vVK)
t=1
<
exp( -16? (62/(44²)))
t=1
exp( -
< (1 - expeexp(-20 - (espp-e//44o27) (4002
Here, the second inequality is by standard Hoeffding bound, and the last inequality is by noting that are summing geometric sequence.
Then, can choose some suitable with o = ensures Pr[Ea] < 0.1 and that Pr 0.9.
Lemma 31. For some appropriately chosen a = O(E/vKK we have the following lower bound:
Pr|E n E2] (M(exp(-2/o) K-1
39

---

Proof. Since event E1 concerns all a * Odec and event E, concerns daec, we know that events E1 and Eg are independent. As a result,
Pr[E1 n Ez] Pr[EA]Pr(E)
2 Pr
RK-1
=Ω
22/27(E2 2 (T<K)(² exp(-2/07
[exp ((1xxp(22/0))) K-1
where utilize the previous lemmas.
Having obtained the previous three probabilistic lemmas, we now prove crucial lemma which an extension of Lemma [1 to the infinite JF setting. At this point, the key insight introduced in Section plays a central role in the proof.
Lemma 32. Assume event E₁ and Eg holds, then greedy algorithm only choose the decoy arm adec-
Proof. The proof is by induction. Assume by round t, the algorithm have only choose the decoy arm Odec- Note that assuming event E and Eg holds. Consider the reward function Stm given by the empirical means: fe (a) (a) for all A. By the induction assumption, (a Fwarm (a) for each arm a + Adec- Hence, by the definition of Fj and E2, we have
1S Saoc|l2 S
Σ aEA
30
3e
4VK
4
Since Saee is an c-interior with respect to F, we have semp F.
Clearly, ft femp F is the unique minimizer of MSE, (-). To this, for any reward vector f + f.mu
we will have
(a( - |C 0 s (a) m(a)),
with at least one inequality strict for one arm. Hence the regression oracle will choose ft = ft Although seme is not the same fancs its optimal action is Adec when ES and Fg happen. This is because
ft pemp (adec)
(adec)
4 4vK K
fanc (aaac)
4VK K
(faec (Agec)
2VK
4VK
(a)
for all + ddec. where the first inequality follows from the definition of Ez, the first equality follows from the definition of decoy, and the last inequality follows from the definitions of E, and l D
Theorem b) directly follows from the above lemmas.
40


Reviews:
[{"review_id": "2Vgu9QFLmx", "reviewer": "Reviewer_jdLA", "summary": "In this work, the authors provide a characterization of the conditions under which the greedy algorithm can succeed or fail. Specifically, they propose the so-called 'self-identifiability' property as a sharp condition for when the greedy algorithm works. The settings considered include structured bandits (non-contextual MAB), contextual bandits, and contextual decision-making with general feedback.", "questions": "Regarding the general feedback setting, I am wondering whether the results developed in Section 5 can be extended to—or provide more concrete insights into—the graph feedback setting as studied in [1]. Specifically, given a feedback graph $G$, how do the structure of $G$ and the function class $\\mathcal{F}$ jointly influence the success or failure of greedy algorithms? For instance, if $G$ is a complete graph, then the setting reduces to the full-information case, in which the greedy algorithm should succeed for general $\\mathcal{F}$.\n\n\n\n[1] Alon, Noga, et al. \"Online learning with feedback graphs: Beyond bandits.\" Conference on Learning Theory. PMLR, 2015.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. I believe understanding the condition of success for greedy policies is important in both theoretical and empirical aspects; thus, the paper is well motivated.\n\n\n2. This work is a technically dense paper presenting a sharp and complete theory on describing the success/failure of greedy actions across different settings.\n\n\nWeaknesses:\n\n1. The main focus of the paper is the finite reward function class. While results in the general function class setting can be obtained via discretization and various examples are provided in Appendix D, it seems different function classes require different case-by-case treatments. Is it possible to have some unified framework for dealing with general function classes—even only for sufficient conditions?", "was_revised": true, "final_justification": "The questions I raised have been well addressed. I would like to keep my recommendation to accept this paper.", "rebuttal": "We are grateful to the reviewer for their positive assessment and for recognizing our work as a \"technically dense paper presenting a sharp and complete theory.\" We appreciate the insightful questions, which we address below.\n\n\n**1. On a unified framework for general function classes (Response to Weakness 1):**\n\nThis is a crucial point. Our main results (Theorems 1, 2, 3) deliberately focus on the finite case to establish a provably complete characterization—a sharp \"if and only if\" condition that provides the foundational intuition for our work. Such a complete characterization is more challenging to obtain for infinite classes.\n\nHowever, our work in Section 6 on infinite function classes is precisely our proposal for a unified and principled framework. The concept of **$\\epsilon$-self-identifiability** (stronger than self-identifiability, see Definition 7) provides a universal sufficient conditions for the success of Greedy (Theorem 4(a)), while the absence of **$\\epsilon$-interior decoy** (weaker than non-self-identifiability, see Definition 7) provides a universal necessary conditions for the success of Greedy (Theorem 4(b)). This is not a case-by-case treatment but a **single, general characterization designed for all infinite function classes** (the proofs involve new, non-trivial ideas as explained in the last paragraph of Section 6). The gap between our sufficient and necessary conditions is controlled by a tunable margin $\\epsilon$. For most natural function classes, this leaves only a small (formally, an O($\\epsilon$)-fraction) set of instances uncharacterized by our theory. Obtaining a complete characterization that closes this margin for *all* instances of *any* general function class remains a considerably challenging open problem for future research.\n\nMoreover, while we explain our examples in Appendix D using our main finite function class theory (via discretization, which in our opinion is a consistent and powerful method for gaining insights), all our examples for (non-contextual) bandits can also be directly explained using the extended theory in Section 6, namely Theorem 4. In particular, our conclusion \"*On a high level, we prove that decoys exist for 'almost all' instances of all bandit structures that we\nconsider (i.e., linear, Lipschitz, polynomial, and quadratic). Therefore, the common case in all these\nbandit problems is that Greedy fails.*\" can be obtained by directly applying Theorem 4(b) to the corresponding function classes.  In these function classes, if the true function lies in the $\\epsilon$-interior, then there exists a decoy that lies in the $\\Omega(\\epsilon)$-interior, making Greedy fail. We'll be happy to spell out these additional examples in a revision if requested.  \n\n**2. On extending the DMSO results to feedback graphs (Response to Question 1):**\n\nThis is an excellent question that gets to the heart of our general framework's power. Our Decision-Making with Structured Observations (DMSO) setting in Section 5 is, in fact, a strict generalization of the feedback graph model.\n\nIn the feedback graph setting of Alon et al., playing an action $i$ reveals the losses of a set of other actions $N(i)$. This can be directly mapped to our DMSO framework:\n\n- A policy $\\pi$ in DMSO corresponds to choosing an arm $i$ to play.\n- The observation $o_t$ in DMSO corresponds to the vector of losses for all arms in $N(i)$.\n- The model class $M$ in DMSO would encode both the function class $F$ (mapping arms to loss distributions) and the feedback graph structure $G$ (determining which losses are observed).\n\nOur theory then provides a direct answer to the reviewer's question: The success or failure of Greedy would be determined by self-identifiability within this specific DMSO instance. An instance $(M^*, M)$ is self-identifiable if, for any suboptimal policy $\\pi$ (i.e., suboptimal arm $i$), observing its corresponding feedback (the losses of arms in $N(i)$) is sufficient to rule out any model in $M$ where $\\pi$ is optimal.\n\nFor the reviewer's specific example, if $G$ is a complete graph (full-information), then playing any arm reveals all losses. Any suboptimal arm $i$ would be easily identified as suboptimal. Therefore, any such instance is trivially self-identifiable, and our theory correctly predicts that Greedy succeeds, consistent with the full-information case.\n\nOur framework thus provides the conceptual machinery to analyze these graph structures and beyond. More concrete insights by extending our examples in Appendix D to include feedback graphs: decoy existence is the common case for Lipschitz bandits. Essentially, if there exists an arm $a$ that does not observe the true best arm $a^*$ and some vicinity thereof, then $a$ can be a decoy arm. For linear bandits, on the other hand, we get self-identifiability as long as the arms in the neighborhood $N(a)$ span the space.\n\nThank you again for the encouraging review and sharp questions. We hope our answers further clarify the scope and significance of our contributions."}, {"review_id": "qNcs4ByFs1", "reviewer": "Reviewer_eWWm", "summary": "This paper studies the following simple yet fundamental question in the theory of bandits: under what reward structure greedy algorithm will succeed. The authors first show that for multi-armed bandits, greedy succeeds if and only if the reward structure satisfies a certain property called self-identifiability, i.e., for any suboptimal arm $a$, the reward function class implies that $a$ is suboptimal after revealing the true mean reward value of $a$. The authors further extend this result to more general settings, including contextual bandits, interactive decision-making with arbitrary feedback, and the case when the reward function class is infinite.", "questions": "This is more like a suggestion rather a question, but I think the authors could outline the technical challenges of obtaining a tight characterization in the infinite function class setting, together with possible routes to resolve those challenges.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written, and studied a simple yet fundamental question in the theory of bandits.  In the MAB setting, the results are obtained by (i) showing greedy will succeed when the instance is self-identifiable; and (ii) greedy will get trapped on the decoy arm (whose existence would be implied by violating self-identifiability). The authors further extend the notion of self-identifiability and decoy to more general settings, including contextual bandits and interactive decision-making with arbitrary feedback, through a series of more technical involved yet intuitive definitions. \n\nThe main weakness is that the characterization is only complete for finite function class, and there is still a gap between the positive result and negative result for infinite function class. Such a limitation has been clearly discussed in the paper, and personally I do not think such weakness is significant enough to reject the paper.", "was_revised": true, "final_justification": "The authors addressed my concerns, and therefore I would like to maintain my positive score.", "rebuttal": "We thank the reviewer for their thoughtful and positive evaluation, and for noting that our paper studies a \"simple yet fundamental question in the theory of bandits\". We especially appreciate the suggestion to outline the technical challenges involved in extending our characterization to the infinite setting.\n\n**On technical challenges for a tight characterization in the infinite case (Response to Question 1):**\n\nThis is an excellent suggestion. A fully tight \"if and only if\" characterization for arbitrary infinite function classes is very difficult. The first fundamental challenge is that one can no longer rely on the function-gap being strictly positive, which is a cornerstone of our analysis in the finite case. The second fundamental challenge is that Greedy's behavior can be highly unstable in nature. In an infinite class $F$, the algorithm's predictor $f_t$ can fluctuate indefinitely within a continuous region of functions that are all similarly consistent with data yet induce very different greedy action choices. As a result, the intuitive logic of “getting stuck in a decoy and staying there forever” does not directly extend.\n\nOur partial characterization in Section 6, which introduces a \"margin\" $\\epsilon$ via the concepts of $\\epsilon$-self-identifiability and the $\\epsilon$-interior decoy, is our proposed route to address these challenges. The margin $\\epsilon$ serves a dual purpose: it stands in for the now-absent function-gap, and it allows us to deal with the predictor's instability. A key technical insight of our analysis is showing that even if the predictor $f_t$ never settles, the chosen greedy action can remain permanently fixed on an ε-interior decoy arm.\n\nHowever, this is still insufficient for a complete characterization. For many natural function classes, our framework leaves a set of instances, typically of fraction $O(\\epsilon)$, uncharacterized. The boundary between success and failure instances in a general infinite space can be highly complex; success instances can be very close to failure instances, making a sharp separation difficult. Our $\\epsilon$-interior notion is designed to provide a robust buffer around this boundary, at the cost of leaving instances within that buffer \"undecided.\"\n\nObtaining a tight characterization in full generality would likely require a more fine-grained analysis exploiting additional structural properties of the function class $F$, which we believe is a rich direction for future work."}, {"review_id": "lrhaeEYIy6", "reviewer": "Reviewer_Vy9h", "summary": "This paper presents a rigorous analysis of the performance of the greedy algorithm in structured bandit problems, including standard multi-armed bandits, contextual bandits, and decision making with structured observations (DMSO). The authors introduce the novel concepts of self-identifiability and decoy arms to characterize when the greedy algorithm performs well or poorly. The analysis first focuses on a finite function class $\\mathcal{F}$, then extends to the more general and realistic setting of an infinite function class by introducing the relaxed notion of $\\epsilon$-self-identifiability.\n\nThe central theoretical result establishes a dichotomy:\n\n* If the problem instance is (or is approximately) self-identifiable, the greedy algorithm achieves sublinear regret, specifically logarithmic in time.\n* If a decoy arm exists, the greedy algorithm can suffer linear regret with positive probability.", "questions": "The greedy algorithm is known to perform well in smoothed contextual bandits. Can the notion of $\\epsilon$-self-identifiability be connected to this framework?", "limitations": "* The analysis of infinite function classes using $\\epsilon$-self-identifiability is a promising direction, but it remains incomplete. A more thorough characterization or sufficient conditions for this relaxed notion would improve the contribution.\n* There is no empirical demonstration of the proposed ideas. A simulation illustrating the impact of self-identifiability and decoys on the greedy algorithm’s performance would help validate the theory and support its practical relevance.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The theoretical framework presented in the paper is strong and well developed. The concept of self-identifiability offers a principled condition under which greedy algorithms succeed. The idea of a decoy arm is an elegant way to formalize the situations in which greedy algorithms become misled by suboptimal choices.\n\nHowever, the presentation lacks clarity in several places. In particular, the definition of self-identifiability relies on the phrase “fixing its expected reward,” which may be too abstract for readers unfamiliar with function class analysis. A more intuitive explanation of what it means to fix an arm’s expected reward and how this restricts the function class would help improve accessibility. Additionally, the paper would benefit from an early, high-level explanation of why the greedy algorithm succeeds when self-identifiability holds and why it fails in the presence of a decoy.", "was_revised": true, "final_justification": "I keep my rating based on the authors' response.", "rebuttal": "We are grateful to the reviewer for their positive feedback and for recognizing our theoretical framework as \"strong and well developed.\" We will incorporate the reviewer's excellent suggestions to improve clarity in a final version (for example, by adding an intuitive example in Section 3 to concretely show how fixing an arm's expected reward restricts the function class).\n\n**1. On the connection to smoothed contextual bandits (Response to Question 1):**\n\nThis is an insightful question. Prior work has shown that GREEDY performs well in smoothed linear contextual bandits (Linear CB). In Appendix D.2, we leverage **self-identifiability** to provide a principled explanation of this phenomenon and explicitly relate it to the smoothed Linear CB literature in Remark 3.\n\nMore specifically, Lemma 2 in Appendix D.2 shows that self-identifiability is a typical case in Linear CB under a mild assumption on context diversity—essentially, that the feature vectors associated with arms span the space. This condition is substantially weaker than the smoothing noise assumptions required in prior work. This distinction is intuitive: whereas prior work aims to achieve near-optimal regret rates, our goal is to characterize the more fundamental dichotomy between sublinear and linear regret, for which a less restrictive condition suffices.\n\nAppendix D.2 goes further. Lemma 3 presents a case in which self-identifiability fails due to a degenerate context set, causing GREEDY to fail in Linear CB. Such scenarios are excluded by the smoothed Linear CB framework but highlight the fundamental role of self-identifiability. Moreover, Appendix D.2 describes how to discretize the Linear CB problem to fit our main theorems (which require finite function classes). The results are formally proved for the discretized setting (BTW, while we haven't stated so in the paper, variants of these lemmas hold even without discretization, and our proofs in the discretized setting require additional effort).\n\nIn this sense, self-identifiability is a very valuable concept in understanding when and why GREEDY succeeds or fails in Linear CB.\n\nNaturally, since our main characterization applies formally to finite function classes, and we propose **$\\epsilon$-self-identifiability** in Section 6 to address infinite classes directly, one might ask whether smoothed contexts imply not only self-identifiability but also the stronger $\\epsilon$-self-identifiability in Linear CB. If true, this could lead to a fully unified theory for Linear CB without discretization. Unfortunately, significant challenges remain. Most notably, our results in Section 6 (including the definition of $\\epsilon$-self-identifiability itself) are developed for non-contextual bandits, and extending them to the contextual setting remains an open problem. We are interested in pursuing this direction in future work.\n\n**2. On the limitation of the analysis for infinite function classes (Response to Limitation 1):**\n\nWe agree that our characterization for infinite classes is partial, a point we discuss in the paper. As we detailed for Reviewer eWWm, a complete characterization is exceptionally challenging because, in infinite spaces, the fundamental function-gap between distinct functions can be zero, and the behavior of Greedy can be highly unstable. Our \"margin\"-based framework in Section 6 is a principled and non-trivial step toward such a theory, but a complete characterization would require more new ideas and tools, which we leave as a direction for future work.\n\n**3. On the lack of empirical demonstration (Response to Limitation 2):**\n\nThis is a fair point. Our primary focus in this work was on establishing the theoretical foundations and proving the linear vs. sublinear regret dichotomy via a rigorous characterization. While simulations could illustrate our theory, a key challenge is how to do so faithfully without appearing cherry-picked, given the sheer generality of our results. Which particular structures should we focus on, and which problem instances within a particular structure? How to reflect the generality of our theory while keeping the simulations manageable?\n\nA useful contrast is the simulation in Banihashem et al. (2023), which is appropriately specific, focusing on unstructured 2-armed bandits—the same scope as their main theoretical results. We believe the strength of our paper lies in its theoretical generality and rigor.  We are certainly open to exploring simulations focused on specific instantiations in future work."}, {"review_id": "Wg9CbvE5cR", "reviewer": "Reviewer_CpfC", "summary": "This paper characterizes the problems for structured contextual bandits that reaches asymptotic success (or failure) when the greedy policy is applied. The characterization is extended to interactive decision making with arbitrary feedback and a structured bandit with infinite function class.", "questions": "1. Could authors highlight the challenges and newly developed techniques to extend the success and failure condition to DMSO and structured bandits with infinite function class?\n\n2. Can the results be extended to randomized policies with exploration probability bounded by some constant?", "limitations": "Discussions on whether the self-identifiabilty is the exact and unique condition for the success of the greedy algorithm may be helpful. It seems there can be other possible conditions that determines the success or failure of the greedy algorithm.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The results cover general cases that are not studied in previous literature.\n\n2. The novel concepts for hardness are discovered with clear motiviations including Graves-Lai coefficent.\n\n\n**Weakness**\n\n1. Providing the challenges of extending to interactive decision making with arbitrary case and structured bandits with infinite function class may help improve the paper.\n\n2. Applications are limited to greedy algorithm only. Although the greedy algorithm is reasonable in some cases, exploration is widely adopted for most bandit problems.", "was_revised": true, "final_justification": "The responses helped me clearly understand the novelty of the theoretical results.", "rebuttal": "We thank the reviewer for their positive feedback and are glad they recognized the novelty of our concepts.\n\n**On the challenges and techniques for DMSO and infinite function classes (Response to Weakness 1):**\n\nThis is a great question. We are happy to highlight the core challenges and our novel techniques:\n\nFor DMSO (Section 5): The root challenge is that the additional feedback may be correlated with (and hence reveals information about) rewards. Greedy must account for these correlations, not just estimated mean rewards. Our solution is to develop a non-standard variant of Greedy based on Maximum-Likelihood Estimation (MLE) (Eq. 5.1). The analysis then becomes much more technical, requiring us to track changes in log-likelihood and define the \"model-gap\" in terms of KL-divergence.\n\nFor Infinite Function Classes (Section 6): The first challenge is that one can no longer rely on the function-gap being strictly positive, which is a cornerstone of our analysis in the finite case. The second challenge is that Greedy's behavior can be highly unstable in nature. In an infinite class $F$, the algorithm's predictor $f_t$ can fluctuate indefinitely within a continuous region of functions that are all similarly consistent with data yet induce very different greedy action choices. As a result, the intuitive logic of “getting stuck in a decoy and staying there forever” does not directly extend. Our characterization in Section 6, which introduces a \"margin\" $\\epsilon$ via the concepts of $\\epsilon$-self-identifiability and the $\\epsilon$-interior decoy, is our proposed route to address these challenges. The margin $\\epsilon$ serves a dual purpose: it stands in for the now-absent function-gap, and it allows us to deal with the predictor's instability. A key technical insight of our analysis is showing that even if the predictor $f_t$ never settles, the chosen greedy action can remain permanently fixed on an $\\epsilon$-interior decoy arm.\n\n**On whether the results can be extended to randomized policies with exploration probability bounded by some constant (Response to Weakness 2 and Question 2):**\n\nNot really. An algorithm like epsilon-greedy, where epsilon (exploration probability) is bounded away from zero, can easily avoid the permanent traps we identify and achieve sublinear regret (in fact, for 2-armed bandits, epsilon can be as low as $\\omega(1/T)$). Put differently, even a tiny probability of unrestricted exploration easily gets around the type of failure that we discuss. \n\nAs we point out in the Introduction (Lines 18-30), our motivation for studying GREEDY with zero exploration is foundational (GREEDY is basic and, in some sense, desirable) as well as economic (GREEDY reflects a natural dynamics with self-interested users). By understanding when and why GREEDY fails, we can precisely identify when exploration is *necessary*. This, in turn, justifies the role of exploration in bandit algorithms and provides a foundational rationale for bandit research.\n\nThat said, there's a broader open question worth spelling out: regret lower bounds for epsilon-greedy. Results/techniques from Banihashem et al (2023) seem to imply *some* lower bounds, but fall very short from matching the well-known T^{2/3} upper bound. However, this question is open even for unstructured bandits (and even for 2 arms), so it stands to reason to study it without structure. \n\n\n**On whether self-identifiability is the exact condition for success: (Response to Question 1)**\n\nYes—for the GREEDY algorithm, we prove that self-identifiability is both a necessary and sufficient condition for success, provided that:\n(1) we define success and failure in terms of sublinear vs. linear regret, and\n(2) we consider a finite function or model class with a strictly positive function-gap or model-gap.\n\nThe negation of self-identifiability is equivalent to the existence of a decoy (Claim 1), which in turn implies failure (Theorem 1b). Together, our results provide a tight \"if and only if\" characterization for the settings studied in Sections 3, 4, and 5. Any alternative, non-equivalent condition would contradict our theorems.\n\nAs shown in Appendix D, many infinite function classes of interest admit meaningful finite analogs via discretization. Furthermore, in Section 6, we demonstrate that natural extensions of self-identifiability allow for partial characterizations of GREEDY’s success or failure in the infinite setting. For these reasons, while it is possible that other conditions govern GREEDY's behavior in certain infinite cases, we believe self-identifiability is a foundational concept.\n\nWe are happy to incorporate the above discussions into the final version of our paper!"}]

Author rebuttal:

Meta-review: This paper considers the contextual bandit problem with a general class of reward functions. The paper introduces a new notion of the identifiability as the general condition for the success of the greedy algorithm. While similar concerns on the limitation to finite function classes and presentation issues are shared between the reviewers, they largely agreed in the opinion that the importance of the problem and the strength of the result overtake the limitation. I expect that the authors polish the paper in the final version by carefully improving the presentation and explaining the difficulty of the current limitation, as they are well addressed in the rebuttal.
Decision: Accept (poster)