Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

We thank the reviewer for their positive feedback and are glad they recognized the novelty of our concepts.

On the challenges and techniques for DMSO and infinite function classes (Response to Weakness 1):

This is a great question. We are happy to highlight the core challenges and our novel techniques:

For 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.

For 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.

On whether the results can be extended to randomized policies with exploration probability bounded by some constant (Response to Weakness 2 and Question 2):

Not 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.

As 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.

That 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.

On whether self-identifiability is the exact condition for success: (Response to Question 1)

Yes—for the GREEDY algorithm, we prove that self-identifiability is both a necessary and sufficient condition for success, provided that: (1) we define success and failure in terms of sublinear vs. linear regret, and (2) we consider a finite function or model class with a strictly positive function-gap or model-gap.

The 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.

As 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.

We are happy to incorporate the above discussions into the final version of our paper!

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.

On technical challenges for a tight characterization in the infinite case (Response to Question 1):

This 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.

Our 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.

However, 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."

Obtaining 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.

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).

1. On the connection to smoothed contextual bandits (Response to Question 1):

This 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.

More 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.

Appendix 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).

In this sense, self-identifiability is a very valuable concept in understanding when and why GREEDY succeeds or fails in Linear CB.

Naturally, 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.

2. On the limitation of the analysis for infinite function classes (Response to Limitation 1):

We 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.

3. On the lack of empirical demonstration (Response to Limitation 2):

This 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?

A 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.

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.

1. On a unified framework for general function classes (Response to Weakness 1):

This 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.

However, 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.

Moreover, 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 consider (i.e., linear, Lipschitz, polynomial, and quadratic). Therefore, the common case in all these bandit 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.

2. On extending the DMSO results to feedback graphs (Response to Question 1):

This 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.

In 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:

• A policy $\pi$ in DMSO corresponds to choosing an arm $i$ to play.
• The observation $o_t$ in DMSO corresponds to the vector of losses for all arms in $N(i)$.
• 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).

Our 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.

For 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.

Our 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.

Thank you again for the encouraging review and sharp questions. We hope our answers further clarify the scope and significance of our contributions.