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

Summary

The authors consider the problem of contextual bandits with finitely many contexts, stochastic rewards and a directed feedback graph (assumed to contain all self loops) across actions. They study the setting of "complete cross-learning" where the reward feedback of the chosen action is observed across all contexts. In this setting, the authors establish a lower bound of $\Omega(\sqrt{\beta_M(G) T})$ where $\beta_M(G)$ is a graph-dependent quantity which lies between the independence number and the maximum acyclic subgraph of the feedback graph, and prove that this lower bound is tight for a specific class of context sequences by designing an efficient algorithm with a matching regret bound. Furthermore, the authors provide an upper bound for general context sequences with a graph dependence that improves upon the maximum acyclic subgraph, but in general may not be tight.

Strengths

* The authors establish regret upper and lower bounds that constitute a considerable step towards characterizing the minimax regret in contextual bandits with feedback graphs in the complete cross-learning framework. * The authors provide an overview of the hard instance construction which helps the reader understand the difficulty of minimizing regret in this setting. * The idea of incorporating a sequential graph-theoretic zero sum game in a bandit algorithm seems novel and very interesting. * Even though the authors close the gap completely only for specific types of context sequences, they also provide an upper bound for general sequences which improves upon the known upper bounds in the literature.

Weaknesses

* My main issue with the presentation of the main results is with the comparison with the previous related work of [1] (lines 147-148). While the authors do mention that this work considers the setting of feedback graphs over the contexts as well as over the arms, it should be mentioned that it is not how the problem is presented in [1]. Rather, they consider a tabular RL problem in which the states correspond to the contexts, with the crucial difference that the transition between states is governed by some stochastic process. Since in the authors' work there is no assumption regarding the transition between contexts (that is, it could be adversarial), it seems not quite fair to compare their results to those of [1], specifically the regret lower bound. Indeed, the lower bound described by the authors is easily seen to be inapplicable in the setting of [1] as they vary the contexts (or states) in a very controlled adversarial manner. Therefore, I think the authors should emphasize that their lower bound does not provide a strengthening of the lower bound given in [1] for the RL setup. References: [1] Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Reinforcement learning with feedback graphs.

Questions

I would appreciate it if the authors could address my main concern under "Weaknesses" and provide a more careful comparison with the work of [1].

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes.

Summary

In this paper, the authors consider the problem of contextual bandits with a feedback graph, for finite context space. In the presented setting, taking an action reveals the rewards for all neighboring actions in the feedback graph for all contexts. The authors propose $\beta_M(G)$, a theoretical quantity in which $M$ is the number of contexts and $G$ is the feedback graph, with the goal of characterizing the hardness of learning for this class of problems. The authors prove a lower bound of $\Omega(\sqrt{\beta_M(G)T})$ where $T$ is the number of rounds. The authors also present a near-optimal upper bound of $\widetilde{O}(\sqrt{\min (\bar{\beta}(G),m(G))T})$.

Strengths

1. The insights in the paper are interesting, it characterizes the difference between MAB with graph feedback and Contextual MAB with graph feedback, for small and finite context space. 2. The authors present upper and lower bounds for the problem. 3. The algorithmic approach taken to produce both results is elegant, especially the use of the arm elimination technique.

Weaknesses

1. In contextual MAB literature, the main difficulty is that the context space is large, and in each episode, the feedback is revealed only for the current context. In the discussed setting, the feedback is revealed for all contexts. This significantly reduces the inherent difficulty of the contextual influence. Hence, (a) Can you please explain how having a context made the learning harder w.r.t the non-contextual MAB with feedback graph in this setting, conceptually? (b) Have you considered the standard Contextual setting in which only the feedback of the current context is released? Can you adjust your results to this setting as well? 2. It would benefit the reader if an additional explanation of equation (4) will be given. So is for the result stated in Lemma 3.1. 3. Typos - A comment that was left in the text: line 20: "to name a few".

Questions

1. See weakness 1. 2. Can you please explain the conclusions to corollary 1.2? Specifically, the dependency of $I_c$ in the context is unclear to me, and why it implies that $\beta_M(G) = m(G)$. 3. Can you please provide some more intuition regarding the behavior of $\beta_M(G)$, and an example for a calculation of it for simple graphs?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

-

Summary

This paper studies contextual online learning when the feedback received by the learner is regulated by a feedback graph. The setting is as follows: the actions constitute the nodes of a directed graph $G$, and playing action $a$ at time $t$ when the context is $x_t$ reveals not only the loss incurred by that action at that time, for that context but the losses of all the neighboring actions, for all possible $m$ contexts. While the contexts are generated adversarially, the losses are i.i.d.. The non-contextual problem is well understood, with tight minimax regret guarantees holding for both the adversarial and stochastic settings. These rates depend on both the time horizon $T$ and some graph parameters. In particular, for strongly observable graphs (as the ones studied in this paper), the rate is known to be $\sqrt{T \alpha}$, where $\alpha$ is the independence number of the feedback graph. Previous results achieve a regret bound of $O(\sqrt{T m})$ for the contextual problem, where $m(G)$ is the maximum acyclic subgraph number, which is complemented by the abovementioned $\Omega(\sqrt{T \alpha})$ lower bound. This paper investigates the gap in the graph-dependent parameter in the minimax rate. Note, $\alpha$ = $m$ for undirected graphs. The contribution of the paper are as follows: when the number of contexts is large ($\ge m$), then the $\sqrt{T m}$ rate is tight in general, a lower bound of $\Omega(\sqrt \beta_m)$ is proved, where $\beta_m$ is a new graph parameter which crucially depends on the number $m$ of contexts and gracefully interpolates between $\alpha$ and $m$. improved upper bounds are then proved for special context sequences and the general problem

Strengths

1. Online learning with feedback graphs is a relevant problem with a long literature in NeurIPS and ICML 2. Studying this problem with contexts is fairly natural, and has already been studied 3. the paper presents a consistent set of results and manages to present them nicely in the intro. Due to space constraints, the technical parts are, however, only roughly sketched.

Weaknesses

- the problem is not closed: there is still a significant gap in the right graph theoretic parameter - the result only holds in the stochastic setting. What can be said in the adversarial setting? - the lower-bound construction is fairly natural (at a high level) - the graph theoretic parameter introduced is artificial and way less natural than the ones present in the non-contextual settings. Minor comments - please update the references: e.g., Schneider and Zimmert and Zhang et al have been published - please consider adding some further references to the learning with feedback graph literature. (see also questions)

Questions

What is the relationship between your graph parameter and the ones in Eldowa et al ”On the Minimax Regret for Online Learning with Feedback Graphs”. NeurIPS 2023?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

No potential negative societal impact

Summary

In this work, the authors consider the problem of contextual bandits with feedback graphs and aim to achieve a tighter dependency on graph-dependent quantities. Figuring out the correct dependency on graph-dependent quantities is a notably challenging problem in the standard MAB framework, as aspects such as whether the feedback graph is directed, whether it has self-loops, or whether the time horizon is large compared to the size of the graphs are crucial components to figure out how much information can be extracted from the feedback graph.\\ In this work, the authors consider a contextual MAB problem where there is a feedback graph across actions and cross-learning between contexts. The authors propose a minimax lower bound for this context, which depends on a quantity $\beta_M(G)$, where $M$ is the number of contexts. The authors then show that this lower bound is tight for certain classes of problems such as self-avoiding contexts, which is a problem setting where the environment regularly switches from one context to the next but doesn't ever come back to contexts that have already been seen in the past. The authors also derive an upper bound in the general setting using a different algorithm.

Strengths

The authors propose a detailed characterization of the challenges of contextual MAB with feedback graphs by focusing in deriving a lower bound and gaining a good sense of how challenging the problem is. They then provide both an algorithm in a setting where they can achieve a tight bound as well as a general algorithm. The proofs are well detailed, and the authors properly study and discuss the gap between upper and lower bounds as well as possible extensions.

Weaknesses

While the gap in terms of upper and lower bounds may be tight in terms of the graph-dependent quantities in settings with self-avoidant contexts, the upper bounds contain some superfluous logarithmic dependencies. (In particular the $log^2 K$ term in Theorem 3.3). Do you think that this could be avoided?

Questions

See weaknesses. You propose a specific algorithm for the setting with self-avoidant contexts, but do you think it is a realistic assumption to make ahead of time? Do you think that it would be possible to get some sort of best-of-both-worlds guarantees, where the same algorithm could achieve tight bounds if we are in the self-avoidant setting while still ensuring worst-case guarantees in the general case?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Theoretical work, NA

Summary

This paper investigates the problem of stochastic contextual bandits with graph feedback, in which a graph over actions models the feedback structure. The learner selects an action after observing the current context, and then receives the losses of the actions that are neighbors of the selected one in the feedback graph. This work proposes a novel graph-theoretic quantity $\\beta\_{M}(G)$ to characterize the statistical complexity of learning in this problem setting. The authors establish a minimax regret lower bound $\\Omega(\\sqrt{\\beta\_{M}(G)T})$, where $\\beta\_{M}(G)$ interpolates between the independence number $\\alpha(G)$ and the maximum acyclic subgraph (MAS) number $m(G)$. Specifically, $\\beta\_{M}(G) = \\max \\{\\sum\_{c=1}^{M} |I\_c| : I\_1, \\dots, I\_M \\text{ are independent sets in } G, I\_i \\nrightarrow I\_j \\text{ for } i < j\\}$. This result implies that, while $\\alpha(G)$ dictates the complexity in multi-armed bandits (i.e., $M=1$), $m(G)$ becomes the relevant parameter as the number of contexts increases. The paper further provides algorithms that achieve near-optimal regret bounds $\\tilde{O}(\\sqrt{\\beta\_{M}(G)T})$ for self-avoiding context sequences and $\\tilde{O}(\\sqrt{\\min\\{m(G),\\bar\\beta\_{M}(G)\\} T})$ for general context sequences (where $\\bar\\beta\_{M}(G)$ is a larger but similarly defined graph parameter than $\\beta(G)$), leveraging carefully designed arm elimination techniques. These algorithms are polynomial-time and demonstrate tight regret bounds for special families of context sequences and feedback graphs, namely undirected or transitively closed graphs.

Strengths

The most interesting contribution of this work is probably the connection between the learnability of the problem and the novel (at least to the best of my knowledge) graph-theoretic parameter $\\beta_{M}(G)$. Thanks to this, the authors are able to provide further insights into the contextual bandit problem with feedback graphs (with complete cross-learning and under the assumption), showing that the number of contexts can influence the dependence of the regret on the structure of the feedback graph $G$, interpolating between the independence number $\\alpha(G)$ (when $M=1$) and $m(G)$ (e.g., when $M \\ge m(G)$. The way the regret analysis shows the dependence on such a parameter, via the computation of the value of the sequential game described in Section 3, is also interesting and nontrivial.

Weaknesses

What the authors consider in this work is not the entire family of strongly observable feedback graphs (the one known to correspond with minimax regret of order $\\sqrt{T}$ in the non-contextual case), but only a subset of those graphs, i.e., that contain all self-loops. This excludes relevant feedback graphs such as the loopless clique and the apple tasting one. I think a discussion about these missing graphs, e.g., in Section 4.1 would give a clearer picture of the contributions of this work and how they compare with previous relevant work. More importantly, the only nearly tight bounds for the regret are provided for self-avoiding contexts. Moreover, the setting of complete cross-learning studied in this work seems quite restrictive as it imposes the assumption of observing the reward of the chosen action under any context. This feels like a somewhat limiting assumption, as in real-world scenarios such a reward is often observed for the current context only, and the same context could reappear in non-contiguous time steps. The applicability of the results is nevertheless sufficient, especially given some applications of interest and the extension of their results for the more general setting, albeit lacking a nearly optimal characterization for general context sequences and any strongly observable feedback graphs. A further limitation of the applicability of the results is the fact that the feedback graph is assumed to be fixed. This might not be the case generally speaking, as feedback graphs could be time-varying (as assumed in most of the recent literature on bandits with feedback graphs). Time-varying feedback graphs could also be found in applications such as repeated first-price auctions (e.g., see “The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations” by Cesa-Bianchi, Cesari, Colomboni, Fusco, and Leonardi, STOC 2024), which is one of the applications mentioned in the related work within this paper.

Questions

- Please, address any relevant doubt that might have arisen from what is written above. - Can the results be extended to the other strongly observable feedback graphs (i.e., the ones not containing all self-loops)? What could be the technical limitations, if you see any? - Do you think it could be possible to adapt the algorithmic techniques in this work for time-varying graphs? Minor comments/typos: - Throughout the paper, use “domination number” instead of “dominating number” - Line 84: “In what follows” instead of “In the sequel” - Some references mention the arXiv, while they might already be published in some conference or journal - I think the introduction would benefit from a more thorough comparison with the literature on bandits with feedback graphs. For instance, detailed studies on the minimax regret for bandits with feedback graphs have been pursued in: - Chen, Huang, Li, and Zhang. “Understanding bandits with graph feedback”, NeurIPS 2021 - Eldowa, Esposito, Cesari, and Cesa-Bianchi. “On the minimax regret for online learning with feedback graphs”, NeurIPS 2023 - Chen, He, and Zhang. “On interpolating experts and multi-armed bandits”, ICML 2024 - Lines 157-159: the following paper also fits with that description: - Zhang, Zhang, Luo, and Mineiro. “Efficient contextual bandits with uninformed feedback graphs”, ICML 2024

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

N/A