Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper describes an algorithm for achieving sublinear `\alpha-'regret for the problem of graphical bilinear bandits introduced by Rizk etal '21. The algorithm is based in the well-known optimism under uncertainty principle. Further they do some modification on some of the problem-dependent parameters to achieve better regret guarantees. They show some numerical results to support their claims. 
strengths_and_weaknesses: + The paper attempts to tackle the regret minimizing aspect of the graphical bilinear bandit problem, which is a positive contribution.
+ The paper is clearly written, defining the quantities of interest and citing appropriate literature works.
+ Experiments show their claims of changing the parameter values which support their claims

- The problem setting introduced is not novel, however this is not a major concern for me.
- The algorithms introduced are somewhat the first choice that one would follow for solving a regret minimization metric for this setting. It would be great if the authors make a small section on the technical challenges faced (and how they overcome them) while adapting the OFUL algorithm to their setting.
questions: 1) Regarding the analysis novelty: please see the comment above on technical novelty.

2) Since I am not very well versed on this topic, are their attempts to show any lower bounds for this problem setting? If not, is there a fundamental difficulty in showing such bounds?
limitations: I agree that the authors are transparent that the paper draws connections with existing works by Rizk etal and Abbasi yadkori etal 2011. However given these already existing works, the contributions made in this paper are not very surprising to me.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper claims to analyze the first regret-based approach to the Graphical Bilinear Bandits problem, where n agents in a graph play a stochastic bilinear bandit game with each of their neighbors. They showed that the setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. The authors present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of the α-regret which characterizes the dependence of the graph structure on the rate of convergence. Experiments are provided in support of their claim.

strengths_and_weaknesses: Strength: 
- The alpha regret formulation and setting of bilinear bandit is well motivated since the original problem is NP-hard (Rizk et al,21).
- Theoretical regret guarantees
- Experimental evaluation

Weakness: 
- Motivating applications are missing that fit the linearity framework
- Technical novelty: The proposed algorithmic idea posed the bilinear problem as a linear problem in d^2 dimensions to the best of my understanding. The remaining challenge is to lift the techniques from the d-dimension linear bandit problem and apply it to the current setting. 
- Optimality guarantees are not tight?
- No comparisons with state-of-the-art bilinear optimization routines, e.g. As pointed out, we can pose the problem as a linear bandit problem in O(d^2) dimension, so in that case, I am curious to understand how the regret and runtime performance of the proposed methods compare against existing linear bandit algorithms, Thompson sampling or OFUL? 
questions: The O(d^2) dependency on regret is believed to be not tight in general. Can the authors comment on the tightness of the upper bound guarantee (for Thm 3.2 and 4.1)?
In the algorithmic ideas or regret analysis, is there a new idea that is specific to this setting distinct from what has been already explored for the linear bandit scenario?
limitations: See points for Weaknesses listed above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper addresses the problem of bilinear bandits with graphical structure. In this problem, the agent must attribute at each round $t\leq T$ an action $x_t^{(i)}$ for each node $i$ of a graph. Then, he receives an expected reward $\sum_{(i,j) \in E} x_t^{(i)} M_* x_t^{(j)}$, where $M_*$ is an unknown matrix, and E is the set of edges of the graph. 

Even in the case where $M^*$ is known, the problem of finding the best action is known to be NP-hard. For this reason, the authors focus on the problem of minimizing the $\alpha$-regret for some $\alpha \in [1/2,1]$, i.e. the difference between $\alpha$ times the cumulative reward of the oracle agent, and their reward. They present two algorithms for this problem, and establish bounds on their $\alpha$-regret. They also study its empirical properties on simulated datasets.
strengths_and_weaknesses: Originality : This problem addresses a well motivated problem of bilinear bandits with a graph structure. While this problem is related to that of bilinear bandit, the parallelization changes the nature of the problem. This problem has already been studied with the objective of finding the best action, as well as in the linear setting, and some proof technics are common to these results.

Clarity : This paper is very well written, pedagogical, and the arguments are well explained.

Significance : This paper addresses a well-motivated problem that had not been studied previously.

Quality :  This paper is very well written, and addresses a problem not solved before. The numerical experiments are convincing.
questions: Can the author please either include a proof of Proposition 3.1 (regarding the efficiency of Max-Cut approximation), or provide a reference proving it?

Could you provide a reference more explicit for lower-bounding the probability of the critical covariance inequality? For the sake of completeness, it would be interesting to include a (sketch of) proof of this result.

I believe there might be a typo in the definition of $\epsilon$ in Theorem 4.1. It should be defined as $\frac{\Delta}{\sum \langle z_*^{(i,j)} \vert \theta_*\rangle}$, instead of $\frac{\Delta}{\sum z_*^{(i,j)}}$.
limitations: The authors discuss possible extensions of their work.
review_title: null

Meta-review: metareview: We thank the authors for their submission.

In this paper, agents are vertices on a graph where an edge between agents i,j indicates that they play a multi-armed bandit game against each other, where the expected reward is bilinear in both agents' actions. The goal is to maximize the total expected reward over all edges of the graph, and prior work shows that this is an NP-hard problem.
Contribution: efficient optimism-based algorithms for minimizing $\alpha$-approximate regret, thus circumventing the computational hardness. 
Considering approximate regret in this setting is a novel approach. 
The paper is clearly written and presents a convincing experimental evaluation.
confidence: Certain
Decision: Accept