Stochastic contextual bandits with graph feedback: from independence number to MAS number

We thank the reviewer for highlighting the difference between [1] and our work. Indeed [1] primarily studies the RL setting so their upper bound is more general than ours; however, our lower bound instance could be embedded into the tabular RL setting of [1]. Consider an episodic tabular RL with $H = 1$, so that the initial state at every episode is the context. Since the initial state can be adversarially chosen in [1], our lower bound construction is legitimate in this setting and could lead to better dependence on the graph structure. The general H can also be handled using an absorbing state. We will provide a more detailed comparison in the final version.

We thank the reviewer for the review and the insightful questions.

1.(a). In general, the oracle we compare in contextual bandits to is able to take different optimal actions under different contexts, so it is a stronger benchmark. Also, our work assumes adversarial context, so intuitively, a larger number of contexts increases the adversary’s ability to break the learner’s exploration plans and to craft a “harder” problem instance. The latter corresponds to increasing $M$ in the lower bound quantity $\beta_M$ and thereby including extra independent subsets in the hard instance.

1.(b). Yes it is straightforward to extend to the case with no information across contexts (by running $M$ instances of the single-context algorithm), which essentially becomes $M$ separate subproblems and leads to an optimal regret $\widetilde{O}(\sqrt{M\alpha T})$.

1.(c). It is however an interesting question when the feedback across contexts is not complete. Section 4.1 discusses the product graph case for weakly observable action graphs. We define product graphs as $(a_1, c_1)\rightarrow (a_2,c_2)$ if $a_1\rightarrow a_2$ and $c_1\rightarrow c_2$ in their respective graphs (we'll make this definition clearer in text). When the action graph is strongly observable, we may extend our Theorem 1.1 and 1.3 with the following graph quantity (defined by both the action graph and the context graph) that shares the same spirit:

and Theorem 1.4 with

where $V_c=\lbrace (a,c): a\in[K] \rbrace$.

2. One can think of Eq (2) of $\beta_M$ as sequentially taking out one independent subset (and its out-neighbors) as the hard instance for a context. Note those $I_c$’s are allowed to be empty. By the constraint of $I_j \not\rightarrow I_k$ for $j<k$, they form a DAG on the set level, so their total size cannot exceed the MAS number $\mathsf{m}(G)$. Then when $M\ge \mathsf{m}(G)$, one can simply take the max acyclic subgraph and put one node for each $I_c$, while leaving $(M-\mathsf{m}(G))$ of them empty. This shows $\beta_M=\mathsf{m}(G)$ when $M$ is sufficiently large, hence Corollary 1.2.

3. As an example, consider a “monotone” graph across the actions: for actions in $[K]$, there is an edge $i\rightarrow j$ iff $i<j$. With cross-learning among $M$ context, the quantity $\beta_M=\max\lbrace M, \mathsf{m}(G)\rbrace$ increases from $\alpha=1$ to $\mathsf{m}(G)=K$ as $M$ grows. This example shows up in bidding in auctions (see Han et al. 2020 in our reference) with actions modeling the bidding values and contexts the values of the presented items.

I thank the authors for their response and have no further questions.

We thank the reviewer for the review and the insightful questions.

1. Our work assumes adversarial context. When the reward is also adversarial, as shown in (Balseiro et al. 2019), cross-learning is not helpful and the optimal minimax regret is proved to be $\sqrt{M\alpha T}$: this essentially corresponds to dividing the horizon into $M$ different subproblems each with duration $T/M$. Then the minimax regret for each (single-context) subproblem is known to be $\sqrt{\alpha T/M}$.
2. (Eldowa et al. 2023) studies the non-context (or single-context) setting and arrives at the independence $\alpha$ number. Our proposed quantity $\beta_M$ can be seen as an extension of $\alpha$ under the assumption of adversarial context, as it sequentially takes the max independent subset and its neighbors. The information-flow constraint in Eq (2) then naturally arises from this adversarial assumption too.
3. We agree that the idea behind the lower bound construction is natural, but we’d also like to make two remarks. First, this natural construction proves the tightness of the MAS number when the context space is large, an observation overlooked in the literature even when the upper bound using the MAS number was obtained. Second, the proof technique requires to achieve a careful balance between exploration and exploitation, and the two-inequality approach (below Line 182) could be of general interest when proving interactive lower bounds.
4. Although our graph-theoretic quantity $\beta_M$ is not as natural as the independence number and the MAS number, our lower bound shows that this is the right quantity for contextual bandits (at least under self-avoiding contexts). In addition, this quantity exhibits the desired interpolation between the independence number and MAS number.
5. We appreciate the reviewer for mentioning these references and shall include them and further discussion in the paper.

We thank the reviewer for the review and the insightful questions.

1. While we agree it is possible to improve the logarithmic $\log(MKT)$ term with a more careful concentration argument, it is less obvious how to avoid the $\log^2K$ term when we use a practical algorithm: if we are allowed access to the dominating subset of the active set of arms, as mentioned in Lemma 3.1, we are only left with $\log K$ term. This term comes from Lemma A.1 and that we include both dominating subsets and independence subsets in the subroutine of Algorithm 1 in order to relate our exploration sets to independent sets. We are not sure this can be removed in our approach.
2. While we include it more as a mathematically interesting case, we wish to point out that our bounds are also tight when the graph is undirected or transitively closed (Theorem 1.4), which is an often more realistic assumption. It is achieved by the more straightforward Algorithm 2 which just greedily picks the active arm with most out-going edges in the subroutine. As an example, in bidding in auctions where the winning bid is revealed, the feedback graph is transitively closed across the learner’s actions (e.g. Han et al. 2020 in our reference).
3. This is a great question. In our Example 1, while the quantity $\beta_{dom}$ used in bounding Algorithm 2 (Lemma 3.2) is loose, Algorithm 2 itself actually achieves the optimal regret under appropriate tie-breaking strategy. It is open whether we can arrive at a tighter bound for Algorithm 2 directly or with modifications, such as exploring an extra small independence subset as we did in Algorithm 1 (details in Appendix C.1).

We thank the reviewer for the thorough review and insightful questions.

1. It is indeed a great question about extending to the class of all strongly observable graphs, and it turns out that the extension is straightforward.

Upper bounds: A key implication of strongly observable graphs is that for any subgraph with size > 1, there is a dominating subgraph. In Sec. 3 we may safely assume the subgraphs are larger than 1 because having a singleton active subset in arm elimination means it is the optimal arm with high probability. In addition, Lemma A.1 and A.2 still hold for strongly observable graphs. Therefore, the minimax quantities in Section 3 remain to hold.

Lower bound: The same lower bound still holds, after adding an additional requirement that $I_1, …, I_M$ are disjoint in the definition of $\beta_M(G)$ in (2). In fact, for strongly observable nodes with no self loop, they cannot appear in $I_2, …, I_M$, and if they appear in $I_1$ we must have $|I_1| = 1$. Therefore, our lower bound analysis still works through.

2. We agree that the assumption of self-avoiding context is often restrictive in applications, and we include it as a mathematically interesting case. However, we wish to point out that our bound is also tight under the assumption of undirected or transitively closed graphs (Theorem 1.4) with the easier-to-implement Algorithm 2. We believe this assumption finds a wider range of applications, such as bidding in auctions where the feedback graphs are transitively closed (e.g. Han et al. 2020) and also possess complete cross-learning.

3. We agree that an incomplete cross-learning is an interesting open question, and discuss it partially in Section 4.1 with weakly observable context-action product graphs. We define product graphs as $(a_1, c_1)\rightarrow (a_2,c_2)$ if $a_1\rightarrow a_2$ and $c_1\rightarrow c_2$ in their respective graphs (we'll make this definition clearer in text). When the action graph is strongly observable, we may extend our Theorem 1.1 and 1.3 with the following graph quantity (defined by both the action graph and the context graph) that shares the same spirit:

and Theorem 1.4 with

where $V_c=\lbrace (a,c): a\in[K] \rbrace$. 4. We agree and appreciate the reviewer for pointing out our inapplicability to time-varying graphs. The high-level reason is that although the graph feedback is helpful for multi-armed bandits even in the adversarial setting, it is typically not helpful for adversarial contextual bandits. For example, it was shown in (Balserio et al. 2019) that when the rewards are adversarial, even with cross learning it is optimal to handle each context separately, with the optimal regret scaling with the number of contexts. Therefore, while previous literature handles time-varying graphs in an adversarial framework using EXP3-type algorithms, we do not know of the counterpart for arm-elimination-based algorithms. 5. We will fix the typos and update the references pointed out by the reviewer.