Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the Online Linear Optimization (OLO) problem with additional hints (predictions) in which at every round $t\in[T]$, the algorithm can decide to receive the hint $h_t$ to help choose an action $x_t$. Upon committing to the action, a loss vector $c_t$ is revealed and the algorithm incurs the cost $\langle c_t,x_t \rangle$. In case the algorithm had received the hint, it also incurs a query cost of $\alpha |c_t|^2$ where $\alpha$ is a pre-specified constant. While prior works had shown that having access to good hints at every round leads to improved logarithmic regret bound (instead of the standard $O(\sqrt{T})$ regret bound of OLO), this work shows that achieving such improved regret bounds is possible with only $O(\sqrt{T})$ hints. Moreover, they show that $o(\sqrt{T})$ hints would not be enough, and the $\Omega (\sqrt{T})$ regret bound can not be avoided in that case. Finally, some extensions of the framework (including the one which allows for bad hints) and the corresponding regret bound for each setting are provided.
main_review: Main strengths of the work:
- The framework of learning-augmented online algorithms is very well motivated and obtaining improved performance bounds which are both consistent (great performance when the predictions are good) and robust (not much worse than the standard worst-case algorithm when the predictions are poor) is of potential interest to a wide audience.
- The assumption that hints have limited availability is very well motivated in the paper via examples.
- The proposed algorithm is relatively intuitive and it is easy to notice its novelties compared to prior works.

Main drawbacks of the paper:
- The paper is not well-written and it is a bit hard to follow for someone with limited exposure to the literature on this problem. It would have been helpful to discuss the prior algorithms and techniques in more detail (for the reader to get more familiar with the literature) and compare and contrast the proposed algorithm with them. In particular, many of the proof details in the paper are not really insightful and they could have been moved to the appendix to make room for a more detailed literature review.
- The choice of the query cost and its importance needs to be discussed in more detail. In particular, the authors need to mention the query cost of previous works and compare theirs with them. Also, it is not clear whether there are any hard (or soft) budget constraints on the query costs. In other words, I am not sure what amount of query cost is considered acceptable.
- The paper lacks any numerical examples. Even some simple synthetic examples would have been particularly helpful to highlight the contrast in the regret performance of the regime with logarithmic regret ($O(\sqrt{T})$ hints) and the one with the standard $O(\sqrt{T})$ regret ($o(\sqrt{T})$ hints).
- While the authors have provided lots of intuitions throughout the paper (particularly in Section 1 and Section 3), these explanations are written from the perspective of someone who is completely familiar with the literature and they are not really helping the reader get more understanding of the techniques.
- The definitions of perfect, good, and bad hints are also not motivated in the paper. It is not clear to me how these different regimes are defined and why the choices make sense in practice. In particular, given that the algorithm requires offline access to the value $\alpha$, I am not sure how $\alpha$ is chosen in different real-world examples.

****************
Post-Rebuttal Update: Thanks to the authors for their detailed responses to the raised questions, I was convinced about the majority of the concerns and I will raise my score to 6.
limitations_and_societal_impact: The authors have briefly discussed the limitations of their work in Section 7. Also, this theoretical work does not raise any potential ethical or societal concerns in my view.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary:  Prior work has shown that in the online linear optimization problem, if at each round, the learner is provided with a hint on the cost prior to its selection by an adversary, then one can achieve a regret of order $O(\log(T))$. The authors consider the question of how many hints the learner requires in order to achieve such a regret rate. They show that $O(\sqrt{T})$ hints are sufficient by proposing an algorithm that achieves $O(\log(T))$. The proposed algorithm is a combination of Online Gradient Descent (OGD) and Follow The Regularized Leader (FTRL). OGD learns adaptively the probability by which the algorithm decides to query a hint or not, while, FTRL proposes which action to play whenever the algorithm decides not to query a hint. Conversely, the authors also show that with $o(\sqrt{T})$ hints, regret is no less than $\Omega(\sqrt{T})$.
main_review: Overall, this paper is very well presented and the results look clean. The conveyed message is also interesting and clarifies how often should an algorithm query hints in order to achieve $O(\log(T))$ regret. The results seem to be independent of the dimension $d$. Could authors comment on this? Perhaps the dependency would be more pronounced in a bandit setting. Also, does the shape of the action set play any role? 

As a minor remark, in the intuition and outline, could the author clarify in what sense $\Vert c_{1:t} \Vert$ is small or large? this is mentioned multiple times, and $\Vert c_{1:t}\Vert$ si compared to linear order in $t$. It would be very enlightening to the reader if the authors could be more precise here.
limitations_and_societal_impact: I don't see really any potential negative societal impact of this work since it is mostly theoretical. Perhaps the authors could consider looking at potential applications and whether these applications bear any negative impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study online linear optimization (OLO) in a setting where the online algorithm has access to hints. They show that $O(\sqrt T)$ hints is sufficient to guarantee $O(\log T)$ regret, and show an explicit algorithm which achieves this bound, along with a matching lower bound on the number of hints required to get $O(\log T)$ regret. They also show that randomization is required for this kind of result in the constrained setting, but surprisingly is not required in the unconstrained setting. They also show some guarantees to robustness against bad hints and various extensions to other online learning settings.
main_review: The paper is well-written. I have a few questions:

1. Can the authors motivate the model for hints a bit? I am aware it is used in several previous papers, but would still like to understand the motivation behind it a bit better. A more natural model, it seems to me, is that the hint is guaranteed to satisfy $\|h_t - c_t\| < \epsilon$. Instead, the guarantee the authors pick is $(h_t, c_t) \geq \alpha \|c_t\|^2$. Can the authors explain the differences between these models? Is one model strictly stronger or weaker, or more realistic in practice? One weakness of this model for hints is that the $O(\log T)$ regret bound only holds if the hints are not charged to the online algorithm's overall cost - if they were charged, then the algorithm would incur $O(\sqrt T)$ regret (since it uses $O(\sqrt T)$ hints). This seems true for any online algorithm which uses this model for hints. 

2. Can the authors explain a bit what they mean by optimistic regret? It seems that they mean regret bounds which depend on the data-dependent quantity $\sum_{t=1}^T \|h_t - c_t\|^2$. I think it would be helpful to add some discussion about this metric (I looked at a few of the references the authors listed but the exact definition still wasn't clear to me).

3. I notice that the authors focus on online linear optimization (OLO), instead of the more general online convex optimization (OCO). A standard technique in OCO (which I'm sure the authors are well aware of!) is simply to reduce OCO to OLO by feeding the gradients of the costs into an OLO algorithm. Can that technqiue be used here? Do these results say anything about the more general convex setting?

Ultimately, it seems to me that the main advance in the paper is that they show that $O(\sqrt T)$ hints are both sufficient and necessary to get $O(\log T)$ regret; previous work assumed $O(T)$ hints (hints in every round). Nailing down this threshold is interesting and merits acceptance in my view.
limitations_and_societal_impact: No problem here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies how to obtain a good regret bound using only sublinear number of hints for online linear optimization. They show that to obtain $O(\ln T)$ regret, only $O(\sqrt{T})$ number of hints are needed. Moreover, they establish a lower bound showing that $\Omega(\sqrt{T})$ number of hints are necessary to achieve $O(\ln T)$ regret. They also extend their results to various settings such as the presence of bad hints, unconstrained linear optimization, etc.
main_review: - Originality: this paper studies a new problem about how many hints are needed to achieve good regret bound. The analysis connecting to switch-once dynamic regret is interesting and novel.
- Quality: the paper is technical sound. Results are complete for the studied setting.
- Clarity: it is a well-written paper and is easy to follow. Intuitions are well explained with concrete examples. The proof sketch provided are also helpful in reproducing the results.
- Significance: the problem studied is quite important in my point of view. In real application the number of hints are often limited and could be expensive to obtain. Understanding the minimum number of (good) hints needed to achieve certain regret bound is thus valuable.

Some questions:
- Can the results be strengthened to high probability bound (on regret and the number of queries)?
- Is it possible to obtain problem dependent lower bound? For example, how many hints are necessary if we want to obtain regret bound of the form $O(||u||\sqrt{\sum_{t=1}^T||c_t||^2_{\star}})$?
limitations_and_societal_impact: This work is purely theoretically and has no foreseeable societal impact.
review_title: null

Meta-review: Reviewers all agree that this paper makes solid contribution to advancing the understanding
of online linear optimization with hints. Please do incorporate all the writing suggestions
from the reviews into the final version.
Decision: Accept (Poster)