Practical Contextual Bandits with Feedback Graphs

Summary

This paper studies online learning in a contextual setting when a feedback graph determines the feedback received by the learner. Namely, the learner observes all the losses experienced by the actions in the graph-neighborhood of the action it played. Feedback graphs are a well-known feedback model for online learning, and their study in the contextual setting is natural. The paper's main result is a general framework (Theorem 3.1) that reduces the problem to the solution at each time step of a convex program. Then the authors instantiate this general theorem for the strongly observable and weakly observable case, obtaining the same regret rates that characterize the non-contextual version of the problem. The primary technical tool of the paper is the parameter defined in equation (3). Following Foster et al. 2021, the authors use this new formula instead of the bandit one (equation 1) to prove their results.

Strengths

- The problem studied is natural and well-motivated. - The regret bounds match the lower bounds in Alon et al., 2015, so they are tight. - The experimental results and the theoretical guarantees support the claim that a richer feedback structure improves the regret bounds w.r.t. the bandit case. - It is nice that the authors devoted some time to presenting the detailed results for some famous classes of feedback graphs.

Weaknesses

- Once equation 3 is designed, the rest of the paper seems incremental to Foster et al. - Equation 3 needs knowledge of the feedback graph. Therefore the paper works only in the informed setting. - The introductory model entails time-varying feedback graphs, while the results for strong and weakly observable feedback graphs need the graph to be deterministic and known up-front. Minor comment: - uniform the \citet and \citep notation

Questions

None

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above

Summary

The authors consider the adversarial contextual bandit problem with feedback graphs, in the finite function class setting with a realizability assumption, with an access to an online regression oracle. They extend previous approaches for the vanilla contextual MAB setting in order to obtain regret bounds of $\tilde{O}(\sqrt{\alpha T})$ with fully observable graphs and $\tilde{O}(d^{\frac13} T^{\frac23})$ for weakly observable graphs, where $\alpha$ and $d$ denote the graph's independence number and weak domination number respectively. The authors demonstrate their results empirically and show that their algorithm performs better than existing approaches when side observations are available.

Strengths

* The authors exhibit the first efficient algorithm for contextual bandits with feedback graphs, which obtains near-optimal regret guarantees both in the strongly observable and weakly observable settings. * The techniques utilized by the authors seem to neatly generalize the approach of Foster et al. ('21) to the feedback graph setting, by generalizing the inverse gap technique to solving a convex problem together with utilizing a combinatorial property of the feedback graphs. * The authors demonstrate in several empirical experiments that their algorithm out-performs SquareCB when feedback graphs are present, thus strengthening the idea that better performance can be obtained when side observations are available.

Weaknesses

* This is not a very major issue, but the algorithm suggested by the authors requires knowledge of the feedback graphs' independence number (or a good bound on it), which is a hard quantity to compute in general. This is only a minor point because many previous works in the feedback graphs literature also require knowing such a parameter, but I will remark that some results can be obtained without this knowledge.

Questions

Given the result presented in the paper, a very natural question that arises is whether or not for stochastic contexts and losses, the approach of [2] can be generalized to the feedback setting in order to obtain similar regret bounds, but with access to an **offline** regression oracle. I think such a result would be also very interesting, and I would expect that similar approaches to those that the authors used in this paper would work for extending [2], as their approach also extends SquareCB of [1]. I'd appreciate it if the authors could comment on whether or not they considered the stochastic setting as well, and if they think that they're approach could be used in order to obtain results with an offline oracle. [1] Foster, Dylan, and Alexander Rakhlin. "Beyond ucb: Optimal and efficient contextual bandits with regression oracles." _International Conference on Machine Learning_. PMLR, 2020. [2] Simchi-Levi, David, and Yunzong Xu. "Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability." _Mathematics of Operations Research_ 47.3 (2022): 1904-1931.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This work is concerned with the problem of contextual bandits with graph feedback. The authors consider a setting where the contexts and the graphs are generated in an arbitrary manner and revealed to the learner at the beginning of each round. For a given context, the mean loss of each arm is assumed to be fixed. Furthermore, it is assumed that the learner is provided with a class of functions mapping context-action pairs to their mean loss, and that this class contains the true function. Following prior works in contextual bandits, the authors use an online regression oracle to estimate the true mean losses. These estimates are then used within the estimation-to-decision framework of Foster et al. (2021). Within this framework, the proposed algorithm requires solving a convex program at each round, for which closed form solutions are provided for special cases of interest. The authors prove regret bounds that depend on the structure of the feedback graphs and the regret of the online regression oracle. Additionally, empirical evaluations are carried out to showcase the algorithm's ability to take advantage of the side observations provided via the feedback graphs.

Strengths

Although the adopted approach relies on existing techniques, the application of the estimation-to-decision framework of Foster et al. (2021) for bandits with graph feedback is still an interesting contribution. Most notably, in Theorems 3.2 and 3.4, the authors bound the decision estimation coefficient for their algorithm in terms of the independence number for strongly observable graphs and the weak domination number for weakly observable graphs, which respectively are the graph theoretic quantities that characterize the minimax regret for these settings. Overall, the paper is well written, the setting is adequately motivated, and the clarity of the presentation is decent.

Weaknesses

- The regret bounds in Corollaries 3.3 and 3.5 are stated in terms of a uniform upper bound on the independence number or the weak domination number of the observed graphs. This is unsatisfactory since a single sparse graph could render the bound vacuous. - In the formulated setting, the graphs are allowed to be stochastic, where each edge is realized with a certain probability which is revealed to the learner at the beginning of the round. However, all the provided theoretical results are for deterministic graphs. - One point in need of clarification concerning the experiments is that it is mentioned in the beginning of Section 5 that all the graphs used in the experiments are deterministic, while the experiment described in Section 5.2.1 seems to involve stochastic graphs. - For the experiment of Section 5.1, it might be more informative to include more intermediate cases between bandits and full information. - A minor correction: In the discussion section, the authors address the limitation of their approach in the uniformed setting, where the feedback graph is only revealed to the learner after making a decision. The authors then cite results for the non-contextual case from (Cohen et al, 2016). However, in that work, the graph is never revealed to the learner, only the actions in the neighbourhood of the played action and their losses are observed.

Questions

- Is it possible to obtain bounds that scale with the average independence number (or weak domination number) of the graphs perhaps via an adaptive choice of the value of gamma at each round? - What kind of regret bounds can we obtain for stochastic graphs using this approach? - Does the proposed approach offer an advantage over existing algorithms for learning with graph feedback in the non-contextual case?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors did address some of the limitations of their work. Notably the fact that their approach requires the knowledge of the feedback graph before choosing the action.

Summary

This work studies the contextual bandits problem in the presence of a feedback graph G_t. An edge (i -> j) in G_t means that taking action a_i allows us to observe the loss for action a_j. The work extends the SquareCB algorithm to this setting, the primary difference being the way the action sampling probability p_t is learned (Eq. (1) vs Eq (4)). The authors also present regret bounds for strongly observable and weakly observable graphs where the bounds improve over the standard contextual bandits setting when the independence number and cardinality of the dominating set is small.

Strengths

- Overall I found the paper to be well-written where the setup was explained well and the notation was easy to follow. - This paper builds on the SquareCB algorithm. I appreciated the fact that the work makes an effort to try to separate their own contributions from the SquareCB paper. - The paper covers both strongly and weakly observable graphs. In general, the statements in Theorems 3.2 and 3.4 are fairly intuitive.

Weaknesses

- By and large, the paper relies heavily on the SquareCB paper's analysis. Although the setting of feedback graphs is new, the analysis seems derivative. - I would suggest that the authors provide more intuition behind the proofs of the key theorems. Even though the theorem statements are easy to understand, it would be nice to get some insight into the proofs, and specifically what are steps different from the standard CB regret analysis.

Questions

- Are there any intermediate characterizations of graphs between strongly and weakly observable? In the strongly observable case, for nodes without self-loops, you require an edge from all other nodes. What if there are edges from most nodes (but not all)? Or what if most nodes are strongly observable but not all? Broadly, I am trying to understand how conservative the bounds are when the graphs are weakly observable (but perhaps not too weak). Is the algorithm expected to the complexity of the graph somehow? - Follow-up to the above, the regret bounds take the worst-case graph over all the rounds. You allow the graph to change over t. Does the regret of your proposed algorithm also improve when the graphs are favorable for a large number of time steps? (CB is not my area of expertise so I understand that both of the above assumptions are probably standard for doing regret analysis, but I think experimentally it would be nice to get some insight into how the actual algorithm performs relative to the theoretical regret).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weaknesses part.

Summary

This work studied contextual bandits with feedback graphs. The authors provided an algorithm based on the recent Decision-Estimation Coefficient (DEC) framework that finds the next-step action distribution by solving a minimax optimization problem. To address the issue that the minimax problem is hard to solve, the authors also showed that there exists an efficient implementation of the solver, and the closed-form solution also exists for some special cases. For the experiment, the authors compared the proposed algorithm with a vanilla baseline algorithm that does not utilize the feedback graph information.

Strengths

The presentation is clear. The overall approach to solving the contextual bandits with feedback graph is convincing. The theoretical results are sound.

Weaknesses

The importance of this work remains unclear. The proposed algorithm is very similar to the original E2D algorithm proposed by Foster et al. 2021 with an additional expectation over the feedback graph. The analysis technique is also very similar. The key difficulty in proving the regret of SquareCBG is to build an effective estimate the DEC constant. However, from the proof of Theorem 3.2, it seems that the proof is pretty standard by following the decomposition technique developed in Foster et al. 2021 (like their Proposition 5.1), while utilizing the graph node estimation lemma proposed by Alon et al. 2015. Therefore, I would recommend the authors highlight the main challenge for them to derive the theoretical results. A typo. Line 62, for some action $j$-> $a_t$.

Questions

See Weaknesses.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors addressed the limitations.

Response

I thank the authors for their response. My (positive) evaluation of the paper remains the same.