Towards Best-of-All-Worlds Online Learning with Feedback Graphs
Authors: Liad Erez
Tomer Koren
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Learning
Multi-armed Bandit
Feedback Graphs
Adversarial Corruptions

Abstract: We study the online learning with feedback graphs framework introduced by Mannor and Shamir (2011), in which the feedback received by the online learner is specified by a graph $G$ over the available actions.  We develop an algorithm that simultaneously achieves regret bounds of the form: $O(\sqrt{\theta(G) T})$ with adversarial losses; $O(\theta(G)\mathrm{polylog}{T})$ with stochastic losses; and $O(\theta(G)\mathrm{polylog}{T} + \sqrt{\theta(G) C})$ with stochastic losses subject to $C$ adversarial corruptions.  Here, $\theta(G)$ is the $clique~covering~number$ of the graph $G$.  Our algorithm is an instantiation of Follow-the-Regularized-Leader with a novel regularization that can be seen as a product of a Tsallis entropy component (inspired by Zimmert and Seldin (2019)) and a Shannon entropy component (analyzed in the corrupted stochastic case by Amir et al. (2020)), thus subtly interpolating between the two forms of entropies.  One of our key technical contributions is in establishing the convexity of this regularizer and controlling its inverse Hessian, despite its complex product structure.


Reviews:
[{"review_id": "q3YGr_f8qrx", "reviewer": "Reviewer_ZV4A", "summary": "This paper studies a best-of-all-worlds algorithm for online learning with feedback graphs by incorporating a novel regularizer. The proposed algorithm simultaneously achieves near-optimal regret w.r.t. $T$ in the adversarial setting, stochastic setting and corrupted stochastic setting.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is an interesting problem to find a best-of-all worlds algorithm for online learning with feedback graphs. This paper presents some solid results, but I still have some concerns:\n\n1. The algorithm requires to know the minimum clique covering of the graph, which is impractical in many applications. Also, most previous works on online learning with feedback graphs do not have this requirement.\n\n2. As discussed in section 1.1, the current regret bounds are not optimal.\n\n3. This paper only studies the case where the graph is strongly observable. Is it possible to generalize the results to the case where the graph is weakly observable? (see [1] for the definition of strongly observable and weakly observable)\n\n4. Though the paper mainly focuses on the theoretical results, I suggest the authors to show some numerical results as previous best-of-all-worlds papers [13,27].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "daF5bak-uu", "reviewer": "Reviewer_bWJC", "summary": "This paper considers the problem of online learning with feedback graphs. Feedback graphs tell which losses the learner gets to observe each time an action is chosen.  In particular, special cases include the bandit setting when the graph has no edges, and the full information setting when the feedback graph is a clique.\n\nThe authors derive bounds that scale in terms of the clique covering number of the graph. This clique covering number is the number of cliques (fully connected subgraphs) that are appearing in the graph. This number is useful because each time one arm is picked, the learner can observe the losses of all the other arms that are in the same clique.\n\nReasoning about the problem in terms of cliques is interesting because the exploration vs exploitation trade-off is not the same everywhere on the graph. If we consider each clique as one entity, we have a standard multi-armed bandits exploration vs exploitation trade-off. But then, when considering which action to play within the clique, this is a full information problem as we will get the feedback for all actions within the clique either way.\n\nThe authors then provide a FTRL algorithm that combines the Tsallis entropy (optimal for MAB) and the Shannon entropy (optimal for Full info).  They also mix in a log barrier regularizer to help with the stability of the algorithm. \n\nThe authors derive a single bound that covers simultaneously the adversarial, the stochastic, and the corrupted setting.\nThat bound is near-optimal because of the consideration of the covering clique number rather than the independence number (which basically means that the edges in the feedback graph that are not part of a clique are not taken advantage of), and because the extra log barrier regularization term leads to extra log factors.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied is a combination of the Best-of-All-Worlds line of work that is been widely studied in the past couple of years in multi-armed bandits with the bandits with feedback graphs line of work. This combination appears to be novel.\nTo be completely best of all worlds, the authors may have considered the stochastically constrained adversarial regime rather than solely the stochastic regime.\n\nThe algorithm derived builds upon the widely used FTRL framework and combines different already existing regularizers. Those regularizers have proved to be optimal in their respective settings (Tsallis for the MAB setting and Shannon for the Full info), and they are combined in a way that exploits the feedback graph structure efficiently. \nThe results achieved are interesting, even though they are not actually optimal.\n\n\nThe paper is clearly written and it is nice that some proof sketches are given in the body of the paper. \nThis being said some final discussion about the work is lacking, in particular about the limitations of the work (see the next section for details). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no conclusion and the limitations of the work are not clearly discussed. In particular, what is the intuition regarding closing the gap between the bound scaling in terms of the covering clique number, and the lower bound scaling with the independence number. \n\nOther limitations that should be discussed:\nThe uniqueness of the best arm in intermediate settings.\nNot considering the stochastically constrained adversarial regime. In the MAB setting, Tsallis-Inf is capable to achieve the stochastic bounds in this more general setting. Do the authors think that something similar could be done here? A best-of-all-worlds setting should probably consider that regime too. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "N8PANmSnQK", "reviewer": "Reviewer_3tpU", "summary": "The authors consider the best-of-both-worlds problem in bandits with graph feedback. Similar to [27], they consider stochastic bandits with C adversarial corruption that interpolates between the stochastic setting and the adversarial setting . As a result, they get $\\text{polylog}( T)\\sum_{k\\in K}1/\\Delta_{\\min,k}$ regret in the stochastic setting and $\\sqrt{|K|T}$ in the adversarial setting, where K is a clique cover of G. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper in general is well written, with detailed explanations on deriving the regularizer and concise but informative proof sketch. Although the self-bounding technique, the constant log-barrier term, and some lemmas all appeared in previous works already, combining these together and getting this novel result in bandits with graph-feedback is still highly non-trivial. \n\n- My main concern is on the stochastic part. Basically we have $O(\\log^5(T))$ dependence on the time horizon (if I count correctly), which doesn't look very optimal even if we consider the best-of-both-worlds setting. It looks like the authors hide this and use polylog most of the time, which is fine, but I may would like to hear from the authors regarding the tightness of this bound under the current algorithm and the analysis. \n\n- Related to the comment above, I found the authors tend to represent stochastic bounds in terms of $O(\\sum_{i\\in S}\\log(T)/\\Delta_{i})$ for some set S as $O(|S|\\log(T))$. This seems not a standard representation in the literature, and in fact, technically, not correct. The $1/\\Delta_i$ term can be very large, which is independent of how many i you sum over. Therefore, it doesn't seem right to me the authors simply say the optimal bound is $O(\\alpha (G) \\log T)$ while theirs is $O(\\theta (G) \\text{polylog}~T)$. A more careful comparison between the bound in this paper and the previous work would be helpful for the reviewers to understand the significance. Some papers on stochastic graph bandits such as [1] may also be a paper that the authors can compare with. \n\n- Lemma 1 looks very technical and the authors don't prove it in the main text, either. Thus, It is not very informative to me and I would suggest move it somewhere else and show 3.2 first.\n\n- [17] also uses the clique partition in their Algorithm 1 and the constant log-barrier term. I think the authors may also compare this with their approach.  Some natural question is like whether their algorithm can achieve best-of-both-worlds when replacing the log-barrier with Tsallis entropy. (Note that the corralling trick is also possible using the method in [2])\n\n- As K is commonly used as the number of arms in MAB, I think using $K=\\theta(G)$ is a little bit confusing. Using $\\theta$ as a shorthand of $\\theta(G)$ is clearer to me. $\\kappa$ is also another commonly used notation for this quantity. \n\n[1] Lykouris, Thodoris, Éva Tardos, and Drishti Wali. \"Feedback graph regret bounds for Thompson Sampling and UCB.\"\n\n[2] Foster, Dylan J., Claudio Gentile, Mehryar Mohri, and Julian Zimmert. \"Adapting to misspecification in contextual bandits.\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3buIfhVt6iA", "reviewer": "Reviewer_jtgp", "summary": "This paper introduces a novel bi-level regularization, namely the Tsallis-Shannon entropy, which is a combination of the two types of entropy with a linear shift. The paper proves the lower bound for the Hessian of the new regularization which is a diagonal matrix with positive entries, and thus convexity. By applying the regularization in the \"Follow the Regularized Leader\" framework, the paper derives an algorithm for online learning problems with undirected graph feedback, which is a generalization of the Multi-Armed Bandits (MAB) problem and Prediction with Expert Advice (PEA) problem. The algorithm achieves near optimal regret bounds for both bandits and full feedback problems with adversarially-corrupted stochastic loss setting. The paper also proves a bound for online learning problems with general undirected graph feedback, which is a big step towards a best-of-all-worlds guarantee for this setting.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The regularization proposed in the paper is new and interesting. It seems that this is the first multi-level regularization in such a form that provably achieves best-of-all-worlds type guarantees in online learning.\n2. The algorithm proposed achieves highly non-trivial regret bounds.\n3. The proofs seem quite non-trivial and the ideas might be useful for solving other similar problems. \n4. The writing is clear. It is very helpful that high level ideas and motivations are provided for the technical proofs, making them easier to understand.\n\n\n\nWeaknesses:\n1. The algorithm requires a clique cover of the feedback graph as input but finding a minimum clique cover is hard. In Alon et al. [1], the algorithm does not need such information as input, and the independence number in the regret bounds is not required to be known in advance.\n2. The bound in this paper depends on the clique covering number of the feedback graph, which is weaker than the independence number of the graph in Alon et al. [1]. So it might be sub-optimal even in the stochastic setting.\n3. Some minor typos, e.g. line 95, line 240.\n\nQuestion:\nI am confused about the derivation between line 501 and 502 in the appendix (the 3rd and 4th inequality). Can you provide more details?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper design a novel, bi-level regularization procedure to successfully achieve a best-of-all-worlds regret guarantee. I’ll start with the negatives and them move on to the positives.

On the negative side, all of the reviewers acknowledge that the results in the stochastic setting are suboptimal. Specifically, it is unclear if the exponent of 5 on the $\log(T)$ term is essential or if this dependence could be reduced (it does seem suboptimal). Another issue is that the authors’ algorithm is restricted to a fixed clique covering. All the reviewers agreed that this is a significant disadvantage, as the choice of clique covering influences the stochastic setting regret bound (by way of the minimum gaps in the corresponding cliques), and hence it is not possible for the algorithm to select the optimal clique covering (since the gaps are unknown). This is one reason why some assessments were lower than they originally were. In my view, this is the most significant weakness of this work. Also, the current regret bounds are based on clique coverings, whereas it would be desirable to obtain results based on independence number.

On the positive side, there are important technical advances in this work. All the reviewers (and I) thought that this is a very difficult problem, and the authors do make important first progress on this problem. Their contribution has significant novelty, and even if they have not yet found the right regularizer for this problem, they have taken an important step in this direction. So, to be clear, even making this progress for a fixed clique covering is considered to be significant. Therefore, this paper meets the bar for publication at NeurIPS, and it will be exciting to see what additional progress can be made going forward. For the final version, I would like to stress that the authors follow the advice of reviewer 3tpU regarding avoiding the informal presentation by way of $\theta(G)$. Not all clique coverings are the same, and among clique coverings of the same size, the corresponding regret bounds (based on the minimum gaps) could be very different. On that note, I encourage the authors to mention adaptivity to the best clique covering a good direction for future work.
Decision: Accept (Poster)