Logarithmic Regret from Sublinear Hints
Year: 2021

Abstract:
We consider the online linear optimization problem, where at every step the algorithm plays a point xt in the unit ball, and suffers loss hct, xti for some cost vector ct that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint ht that has non-trivial correlation with ct before it plays xt, then it can achieve a regret guarantee of O(log T ), improving on the bound of ⇥( p T ) in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain O(log T ) regret with just O( p T ) hints under a natural query model; in contrast, we also show that o( p T ) hints cannot guarantee better than ⌦( p T ) regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.

text: p T ) in
the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain O(log T ) regret with just O( p T ) hints under a natural query model; in contrast, we also show that o( p T ) hints cannot guarantee better than ⌦( p T ) regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.

heading: 1 Introduction
text: There has been a spate of work on improving the performance of online algorithms with the help of externally available hints. The goal of these works is to circumvent worst-case bounds and exploit the capability of machine-learned models that can potentially provide these hints. There have been two main lines of study. The first is for combinatorial problems, where the goal has been to be improve the competitive ratio of online algorithms; problems considered here include ski-rental [9, 17], caching [13, 19, 26], scheduling [1, 12, 17, 22], matching [16, 18], etc. The second is in the learning theory setting, where the goal has to been to improve the regret of online optimization algorithms. A series of recent papers showed how to achieve better regret guarantees, assuming that we have a hint about the cost function before the algorithm makes a choice. For many variants of the online convex optimization problem, works such as [25, 8, 2, 3] studied the power of having prior information about a cost function. Works such as [29] have also studied improved regret bounds in partial information or bandit settings. In all these works, a desirable property is to ensure consistency, which demands better performance with better quality hints, and robustness, which guarantees a certain level of performance with poor quality or even adversarially bad hints.
Recall the standard online optimization model [30], which is a game between an algorithm and an adversary. In each round, the algorithm plays a point and the adversary responds with a cost function that is visible to the algorithm, and the cost in this round is measured by evaluating the cost function on the played point. In online linear optimization, the cost function is linear. The regret of an algorithm is the worst-case difference between the cost of the algorithm and the cost of an algorithm
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
that plays a fixed point in each round. A natural way to incorporate hints or prior information is to give the algorithm access to a hint about the cost function at a given round before it chooses a point to play at that round. In this sense, hints are present gratis [25].
The availability of a hint in each round seems natural in some settings, e.g., when cost functions change gradually with time [25, 4]). However, it can be prohibitive in many others, for instance, if hints are obtained by using expensive side information, or if they are generated by a running a computationally expensive ML model. Furthermore, hints can also be wasteful when the problem instance, or even a large sub-instance, is such that the algorithm cannot really derive any substantial benefit from their presence. This leads to the question of strengthening the online learning with hints model by making it parsimonious. In this work, we pursue this direction, where we offer the algorithm the flexibility to choose to ask for a hint before it plays the point. It then becomes an onus on the algorithm to know when to ask for a hint and how to use it judiciously, while ensuring both consistency and robustness. The performance of such an algorithm is measured not only by its regret but also by the number of hints it uses.
Our contributions. We now present a high level summary of our results. For ease of exposition, we will defer the formal statements to the respective sections. All our results are for the problem of online linear optimization (OLO) when the domain is the unit `2 ball; the cost function at every step is defined using a cost vector ct (and the cost or loss is the inner product of the point played with ct). We call a hint perfect if it is the same as the cost vector at that time step, good if it is weakly correlated with the cost vector, and bad otherwise.
As our main result, we show that for OLO in which hints are guaranteed to be good whenever the algorithm asks for a hint, there is an efficient randomized algorithm that obtains O(log T ) regret using only O( p T ) hints. We extend our result to the case when |B| hints can be bad (chosen in an oblivious manner, as we will discuss later), and give an algorithm that achieves a regret bound of O( p |B| log T ), while still asking for O( p T ) hints. It is interesting to contrast our result with prior work: Dekel et al. [8] obtained an algorithm with O(log T ) regret, when a good hint is available in every round. Bhaskara et al. [2] made this result robust, obtaining a regret bound of O( p |B| log T ), when there are |B| bad hints. Our result improves upon these works by showing the same asymptotic regret bounds, but using only O( p T ) hints. Our result also has implications for optimistic regret bounds [25] (where we obtain the same results, but with fewer hints) and for online learning with abstention [24] (where we can bound the number of abstentions).
We also show two lower bounds that show the optimality of our algorithm. The first is regarding the minimum number of hints needed to get O(log T ) regret: we show that any (potentially randomized) algorithm that uses o( p T ) hints will suffer a regret of ⌦( p T ). The second and more surprising result is the role of randomness: we show that any deterministic algorithm that obtains O(log T ) regret must use ⌦(T/ log(T )) hints, even if each of them is perfect. This shows the significance of having a randomized algorithm and an oblivious adversary.
Finally we extend our results to the unconstrained OLO setting (see Section 6), where we design a deterministic algorithm to obtain O(log3/2 T ) regret (suitably defined for the unconstrained case) when all hints are good, and a randomized algorithm to obtain O(log T ) regret, which can be extended to the presence of bad hints.
There are three aspects of our results that we find surprising. The first is even the possibility of obtaining O(log T ) regret using only a sublinear number of hints. The second is the sharp threshold on the number of hints needed to obtain logarithmic regret; the regret does not gracefully degrade when the number of hints is below O( p T ). The third is the deterministic vs randomized separation between the constrained and the unconstrained cases, when all queried hints are good.
We now present some intuition why our result is plausible. Consider the standard “worst-case” adversary for OLO: random mean-zero costs. This case is “hard” because the learner achieves zero expected cost, but the competitor achieves p T total cost. However, if we simply play a hint ht
on O( p T/↵) rounds, each such round incurs ↵ cost, which is enough to cancel out the p T regret while making only O( p T ) hint queries. Thus, the standard worst-case instances are actually easy with hints. More details on this example and an outline of our algorithm are provided at the start of Section 3.
Organization. Section 2 provides the necessary background. The main algorithm and analysis for the constrained OLO case are in Section 3. The extensions and applications of this can be found in Section 4. Section 5 contains the lower bounds and Section 6 contains the algorithms and analyses for the unconstrained case. All missing proofs are in the Supplementary Material.

heading: 2 Preliminaries
text: Let k · k denote the `2-norm and Bd = {x 2 Rd | kxk  1} denote the unit `2 ball in Rd. We use the compressed sum notation and use c1:t to denote Pt i=1 ci and kck21:t to denote Pt i=1 kcik2. Let ~c = c1, . . . , cT be a sequence of cost vectors. Let [T ] = {1, . . . , T}. OLO problem and Regret. The constrained online linear optimization (OLO) problem is modeled as a game over T rounds. At each time t 2 [T ], an algorithm A plays a vector xt 2 Bd, and then an adversary responds with a cost vector ct 2 Bd. The algorithm incurs cost (or loss) hxt, cti at time t. The total cost incurred by the algorithm is costA(~c) = PT t=1hxt, cti. The regret of the algorithm A with respect to a ‘comparator’ or benchmark vector u 2 Bd is
RA(u,~c) = costA(~c) costAu(~c) = TX
t=1
hxt u, cti,
where Au is the algorithm that always plays u at every time step. The regret of an algorithm A is its worst-case regret with respect to all u 2 Bd:
RA(~c) = sup u2Bd RA(u,~c).
Hints and query cost. Let ↵ > 0 be fixed and known. In this paper we consider the OLO setting where, at any round t before choosing xt, an algorithm A is allowed to obtain a hint ht 2 Bd. If hht, cti ↵kctk2, we say that the hint is ↵-good. If A opts to obtain a hint at time t, then it incurs a query cost of ↵kctk2; the query cost is 0 if no hint was obtained at time t. The definition of regret stays the same and we denote it by RA,↵(·). The total query cost of A is given by QA,↵(~c) =PT
t=1 t · ↵kctk2 where t is an indicator function used to denote whether A queried for a hint at time t. Note that the algorithm does not actually know the query cost for a round until the end of the round. If A is a randomized algorithm, the notions of expected regret and expected query cost follow naturally. We consider the setting when the adversarial choice of the hint ht and cost vector ct at time t is oblivious to whether the algorithm queries for a hint at time t but can depend adaptively on all previous decisions.
More generally, we consider the case that some subset of the hints are “bad” in the sense that hct, hti < ↵kctk2; we let B denote the set of such indices t. Although we assume ↵ is known to our algorithms, we do not assume any information about B. Further, our algorithm is charged ↵kctk2 for querying a hint even if the hint was bad.

heading: 3 Main algorithm
text: Intuition and outline. The high-level intuition behind our algorithm is the following: suppose for a moment that ↵ = 1/2 and each hint is ↵-correlated with the corresponding cost. Now suppose the cost vectors c1, . . . , cT are random unit vectors, as in the standard tight example for FTRL. In this case, if an algorithm were to make a hint query for the first 4 p T steps, set xt = ht in those
steps, and play FTRL subsequently, then the cost incurred by the algorithm will be less than 2 p T in the first 4 p T steps, and 0 (in expectation) subsequently. On the other hand, for random vectors, we have kc1:T k  2 p T with high probability, and thus the best vector in hindsight achieves a total
cost kc1:T k 2 p T . Thus the algorithm above actually incurs regret  0.
It turns out that the key to the above argument is kc1:T k being small. In fact, suppose that ct are unit vectors, and assume that kc1:T k  T/4. Now, suppose the algorithm makes a hint query at 10 p T random indices, sets xt = ht in those steps, and uses FTRL in the other steps. One can show that the cost incurred by the algorithm is 5 p T plus the cost of the FTRL steps. Since the cost in the
FTRL steps is within p T of the cost incurred by the competitor u, we can show that the regret is once again  0. The missing subtlety here is accounting for the cost of u on the query steps, but using the bound on kc1:T k, this can be adequately controlled if the queries are done at random. The above outline suggests that the difficult case is kc1:T k being large. However, it turns out that prior work of Huang et al. [11] showed that when the domain is the unit ball, FTL achieves logarithmic regret if we have kc1:tk ⌦(t) for all t. Our algorithm can be viewed as a combination of the two ideas above. If we could identify the largest round S for which kc1:Sk is small, then we can perform uniform sampling until round S and use FTL subsequently, and hope that we have logarithmic regret overall (although it is not obvious that the two bounds compose). The problem with this is that we do not know the value of S. We thus view the problem of picking a sampling probability as a one-dimensional OLO problem in itself, and show that an online gradient descent (OGD) algorithm achieves low regret when compared to all sequences that have the structure of being until a certain time and 0 thereafter (which captures the setting above). The overall algorithm thus picks the querying probability using the OGD procedure, and otherwise resorts to FTRL, as in the outline above.
We now present the details of the overall algorithm (Section 3.3) and the two main subroutines it uses (Sections 3.1 and 3.2).

heading: 3.1 A sharper analysis of FTRL
text: In this section we consider the classic adaptive Follow the Regularized Leader (FTRL) algorithm Aftrl (Algorithm 1) and show a regret bound that is better than the usual one, if the length of the aggregate cost vector grows “rapidly” after a certain initial period.
For convenience, let t = kctk2. Define the regularizer terms as r0 = 1 and for t 1, let
rt = p 1 + 1:t p 1 + 1:t 1. (1)
By definition, we have r0:t = p 1 + 1:t. Furthermore, we have rt < 1 for all t, since t = kctk2  1. The FTRL algorithm Aftrl then plays the points x1, x2, . . . , which are defined as
xt+1 = argmin kxk1
n hc1:t, xi+
r0:t 2 kxk2
o . (2)
Algorithm 1 Adaptive FTRL Aftrl. x1 0, r0 1 for t = 1, . . . , T do
Play point xt Receive cost ct r0:t p 1 + kck21:t
xt+1 argmin kxk1
n hc1:t, xi+
r0:t 2 kxk2
o
end for
Algorithm 2 OGD with shrinking domain Aogd. Require: Parameter p1 0, D1 [0, 1] for t = 1, . . . , T do
Play point pt Receive cost zt and t  1 { t will eventually be set to kctk2} Dt [0,min(1, p1+ 1:t )] ⌘t 1+ 1:t pt+1 ⇧Dt (pt ⌘tzt), where ⇧Dt is the projection to the interval
end for
We will show that Aftrl satisfies the following refined regret guarantee: Theorem 3.1. Consider Aftrl on a sequence ct of cost vectors and let ↵ 2 (0, 1) be any parameter. Suppose that S is an index such that for all t > S, kc1:tk ↵4 (1 + 1:t) (recall t = kctk 2 ). Then,
1. For all N 2 [T ] and for any kuk  1, we have
NX
t=1
hct, xt ui  4.5 p 1 + 1:N .
2. For the index S defined above, we have the refined regret bound:
RAftrl(~c)  p 1 + 1:S
2 +
18 + 8 log(1 + 1:T )
↵ + kc1:Sk+
SX
t=1
hct, xti. (3)
Part (1) of the theorem follows from the standard analysis of FTRL; we include the proof in Appendix B.1 for completeness. Part (2) is a novel contribution, where we show that if kc1:tk grows quickly enough, then the “subsequent” regret is small. It can be viewed as a generalization of a result of Huang et al. [11], who proved such a regret bound for S = 0.

heading: 3.2 Switch-once dynamic regret
text: In this section we show a regret bound against all time-varying comparators of a certain form. More formally, we consider the one-dimensional OLO problem where the costs are zt and 1 is a known parameter. We also assume that at time t, the algorithm is provided with a parameter t 2 [0, 1] that will give some extra information about the sequence of comparators of interest. Thus the modified OLO game can be described as follows:
• For t = 1, 2, . . . , the algorithm first plays pt 2 [0, 1], and then zt, t are revealed. • zt always satisfies z2t  4 t. • We wish to minimize the regret with respect to a class of comparator sequences (qt)Tt=1
(defined below), i.e., minimize P
t zt(pt qt) over all sequences in the class.
We remark that for the purposes of this subsection, we can think of t as z2t . (The more general setup is needed when we use this in Algorithm 3.) Definition 3.2 (Valid-in-hindsight sequences). We say that a sequence (qt)Tt=1 is valid in hindsight if there exists an S 2 [T ] and a 2 [0, 1] such that
1. qt = for all t  S and qt = 0 for t > S. 2. At the switching point, we have 2  2
1+ 1:S .
We now show that a variant of online gradient descent (OGD) with a shrinking domain achieves low regret with respect to all valid-in-hindsight sequences; we call this Aogd (see Algorithm 2). Theorem 3.3. Let 1 be a given parameter, and (zt)Tt=1 be any sequence of cost values satisfying z2t  4 t. Let (qt)Tt=1 be a valid-in-hindsight sequence. The points pt produced by Aogd then satisfy:
TX
t=1
zt(pt qt)  (1 + 3 log(1 + 1:T )) .

heading: 3.3 Full algorithm
text: In this section we present the full algorithm that utilizes the above two ingredients.
Algorithm 3 Algorithm with hints Ahints. Require: Parameter ↵
Initialize an instance of Aftrl and an instance of Aogd with parameter = 10/↵ for t = 1, . . . , T do
Receive pt from Aogd; Receive xt from Aftrl With probability pt, get a hint ht and play x̂t = ht; otherwise, play x̂t = xt Receive ct Send ct to Aftrl as tth cost; Send zt = ↵kctk2 hct, xti and t = kctk2 to Aogd
end for
Theorem 3.4. When B = ;,
E[RAhints,↵(~c)]  78 + 38 log(1 + kck21:T )
↵ and E[QAhints,↵(~c)]  20
q kck21:T .
Proof. Let us first bound the expected cost of querying the hints. From the description of Aogd (Algorithm 2), because of the shrinking domain, we have pt  |Dt 1|  10
↵ p 1+ 1:t 1 . At time t,
the expected query cost paid by the algorithm is pt · ↵ kctk2. Using the above, we can bound this as TX
t=1
pt↵ kctk2  TX
t=1
10 tp 1 + 1:t 1
 TX
t=1
10 tp 1:t  20 p 1:T = 20
q kck21:T ,
where the last inequality follows from concavity of the square root function (e.g., [20, Lemma 4]).
Now we proceed to the more challenging task of bounding the expected regret. We start by noting that the expected loss on any round t is simply E[hct, x̂ti] = pthct, hti+(1 pt)hct, xti. Therefore the expected regret for a fixed u is: TX
t=1
E[hct, x̂t ui] = TX
t=1
pthct, ht xti+ hct, xt ui  TX
t=1
pt( ↵kctk2 hct, xti) + hct, xt ui,
where we have used the fact that the hint ht is ↵-good. The main claim is then the following.
Lemma 3.5. For the choice of pt, xt defined in Ahints (Algorithm 3), we have TX
t=1
pt( ↵kctk2 hct, xti)+ hct, xt ui  78 + 38 log(1 + kck21:T )
↵ = O
✓ 1 + log(1 + 1:T )
↵
◆ .
Assuming this, the bound on expected regret easily follows, completing the proof.
We now focus on proving Lemma 3.5.
Proof of Lemma 3.5. The key idea is to prove the existence of a valid-in-hindsight sequence (qt)Tt=1 (Definition 3.2) such that when pt on the LHS is replaced with qt, the sum is O(log(T )/↵). The guarantee of Algorithm 2 (i.e., Theorem 3.3) then completes the proof. Specifically, since we set = 10/↵ and zt = ( ↵kctk2 hct, xti), Theorem 3.3 guarantees that for any valid-in-hindsight sequence (qt)Tt=1, we have:
TX
t=1
pt( ↵kctk2 hct, xti) + hct, xt ui
 TX
t=1
qt( ↵kctk2 hct, xti) + hct, xt ui+ 10
↵
1 + 3 log(1 + kck21:T ) . (4)
Let us define S to be the largest index in [T ] such that kc1:Sk  ↵4 (1 + 1:S). Firstly, by Theorem 3.1 (part 2), for any such index S we have:
TX
t=1
hct, xt ui  p 1 + 1:S
2 +
18 + 8 log(1 + 1:T )
↵ + kc1:Sk+
SX
t=1
hct, xti. (5)
Let := p 1+ 1:S 2 +kc1:Sk+ PS
t=1hct, xti denote the “excess” over the logarithmic term. Note that by Theorem 3.1 (part 1), for a vector u = c1:Skc1:Sk , we have kc1:Sk+ PS t=1hct, xti = PS t=1hct, xt
ui  4.5 p 1 + 1:S . Thus, we have  5 p 1 + 1:S . Now, note that if 1 + 1:S  100↵2 , we have 5 p 1 + 1:S  50/↵. Thus, by setting qt = 0 for all t (which is clearly valid-in-hindsight), the proof follows. Further, if  1, then clearly we can again set qt = 0 for all t to complete the proof. Thus, we assume in the remainder of the proof that 1 + 1:S > 100 ↵2 and > 1.
Our goal now is to construct a valid-in-hindsight switch-once sequence that has value qt = 2 [0, 1] for t  S and qt = 0 for t > S such that we also have :
SX
t=1
↵ t + hct, xti ! 5 p 1 + 1:S . (6)
First, let us understand the term in the parentheses on the LHS above. We bound this using the following claim. Claim. ↵ · 1:S + P tShct, xti ↵ 2 (1 + 1:S).
Proof of claim. Suppose that we have P
tShct, xti < ↵ 2 (1 1:S). By definition of S, we have
=
p 1 + 1:S
2 + kc1:Sk+
SX
t=1
hct, xti  p 1 + 1:S
2 +
↵ 4 (1 + 1:S) + ↵ 2 (1 1:S)
=
p 1 + 1:S
2 ↵ 4 (1 + 1:S) + ↵.
From our assumption that p 1 + 1:S 10↵ , the RHS above is ↵, which in turn is at most 1. Since we assumed > 1, this is a contradiction so the claim holds.
Thus in order to satisfy (6), we simply choose
= 10
↵ p 1 + 1:S .
By assumption, this lies in [0, 1], and further, for = 10/↵, the (qt) defined above is a valid-inhindsight sequence. Combining the fact that  5 p 1 + 1:S with (6), we have that
TX
t=1
qt( ↵kctk2 hct, xti) + hct, xt ui  18 + 8 log(1 + 1:T )
↵ .
Now appealing to the guarantee of Theorem 3.3 as discussed earlier, we can replace qt with pt by suffering an additional logarithmic term on the RHS. Combining all these cases completes the proof of Lemma 3.5, and thus also the proof of Theorem 3.4.

heading: 4 Extensions and applications
text: In the following subsections, we extend the analysis of Algorithm 3 to disparate settings: we consider robustness to uninformative or “bad” hints, the more classical “optimistic” regret setting, and online learning with abstention.

heading: 4.1 Bad hints
text: First, we extend Theorem 3.4 to consider the case B 6= ; by carefully accounting for the regret incurred during rounds where t 2 B and making crucial use of the shrinking domain Dt. Theorem 4.1. For any B,
E[RAhints,↵(~c)]  78 + 38 log(1 + kck21:T )
↵ + 40
sX
t2B kctk2 +
20
↵
sX
t2B khtk2
q log(1 + kck21:T )
= O p |B| log T ↵ ! , and E[QAhints,↵(~c)]  20 q kck21:T .

heading: 4.2 Optimistic bounds
text: Next, we show that our results have implications for optimistic regret bounds (e.g., [10, 6, 25, 27, 23]). The standard optimistic regret bound takes the form O( qPT
t=1 kct htk2). We will show that the same result can be obtained (up to logarithmic factors) even while only looking at O( p T ) hints. The approach is very simple: if we set ↵ = 14 , then a little calculation shows that for t 2 B, kctk2 + khtk2 = O(kct htk2), so that Theorem 4.1 directly implies the desired result.
Theorem 4.2. Set ↵ = 14 . Then E[RAhints,↵(~c)]  312 + 152 log(1 + kck21:T ) + 80 ✓ 1 + q log(1 + kck21:T ) ◆sX
t2B kct htk2
= O
0
@log(T ) +
vuut TX
t=1
kct htk2 log(T )
1 A , and E[QAhints,↵(~c)]  20 q kck21:T .

heading: 4.3 Online learning with abstention
text: Finally, we apply our algorithm to the problem of online learning with abstentions. In this variant of the OLO game, instead of being provided with hints, the learner is allowed to “abstain” on any given round. When the learner abstains, it receives a loss of ↵kctk2 for some known ↵ but pays a query cost of ↵kctk2. The regret is again the total loss suffered by the learner minus the total loss suffered by the best fixed adversary, which does not abstain. This setting is very similar to the scenario studied by [24] in the expert setting, but in addition to moving from the simplex to the unit ball, we ask for a more detailed guarantee from the learner: it is not allowed to abstain too often, as measured by the query cost. In this setting, our Algorithm 3 works essentially out-of-the-box: every time the algorithm queries a hint, we instead simply choose to abstain. This procedure then guarantees: Theorem 4.3. In the online learning with abstention model, the variant of Algorithm 3 that abstains whenever the original algorithm would ask for a hint guarantees expected regret at most:
78 + 38 log(1 + kck21:T ) ↵ = O
✓ 1 + log(1 + 1:T )
↵
◆ .
Further, the expected query cost is at most 20 p kck21:T .
Proof. Since we abstain with probability pt and otherwise play xt, the expected regret isPT t=1 pt↵kctk2 + (1 pt)hct, xti hct, ui. Thus the regret bound follows directly from Lemma 3.5. The query cost bound follows the identical argument as Theorem 3.4.

heading: 5 Lower bounds
text: In this section we first show that the regret bound obtained in Theorem 3.4 is essentially tight. Next, we show that randomness is necessary in our algorithms. Theorem 5.1. Let ↵ 2 (0, 1] be any parameter, and suppose A is an algorithm for OLO with hints that makes o ⇣p T ↵ ⌘ hint queries. Then there exists a sequence of cost vectors ct and hints ht of unit length, such that (a) in any round t where a hint is asked, hct, hti ↵ kctk2, and (b) the regret of A on this input sequence is ⌦( p T ).
Proof. We will construct a distribution over inputs {ct, ht} and argue that any deterministic algorithm has an expected regret ⌦( p T ) for inputs drawn from this distribution. By the minmax theorem, we then have a lower bound for any (possibly randomized) algorithm A. We consider two-dimensional inputs. At each step, ht is chosen to be a uniformly random vector on the unit circle (in R2). The cost ct is set to be ↵ht ± p 1 ↵2 h?t , where h?t is a unit vector orthogonal to ht, and the sign is chosen uniformly at random. Now for any deterministic algorithm, if A queries ht at time t, then it can play a point aht + bh?t , for scalars a, b. In expectation, this has inner product a↵ with ct, and thus the expected cost incurred by A in this step is ↵ (since |a|  1). If A does not query ht, then ct is simply a random unit vector, and thus the expected cost incurred by A in this step is 0. Next, consider the value minkuk1 P thct, ui, i.e., the best cost in hindsight; this is clearly
k P
t ctk. By construction, ct is a uniformly random vector on the unit circle in R2 (and the
choices are independent for different t). Thus we have E[k P t ctk] ⌦( p T ). (This follows from properties of sums of independent random unit vectors; see Supplementary Material for a proof.) Thus, if the algorithm makes K queries, then the expected regret is at least K↵ + ⌦( p T ). This quantity is ⌦( p T ) as long as K = o ⇣p T ↵ ⌘ , thus completing the proof.
We next show that for deterministic algorithms, making O( p T ) hint queries is insufficient for obtaining o( p T ) regret, even if the hints provided are always 1-good (i.e., hints are perfect). Theorem 5.2. Let A be any deterministic algorithm for OLO with hints that makes at most C p T <
T/2 queries, for some parameter C > 0. Then there is a sequence cost vectors ct and hints ht of unit length such that (a) ht = ct whenever A makes a hint query, and (b) the regret of A on this input sequence is at least p T
2(1+C) .
We remark that by setting C appropriately, we can also show that for a deterministic algorithm to achieve logarithmic regret, it needs to make ⌦ ⇣ T
log T
⌘ queries.

heading: 6 Unconstrained setting
text: Algorithm 4 Algorithm with hints (unconstrained case). Require: Parameters ✏, ↵, K, d-dimensional unconstrained OLO algorithm Aunc, one-dimensional
unconstrained OLO algorithm Aunc-1D guaranteeing (7) for t = 1, . . . , T do
{Randomized version} t 1 with probability min ✓ 1, K
↵ p
1+kck21:t 1
◆ ; 0 otherwise.
{Deterministic version} t 1 iff 1 + Pt 1 ⌧=1 i⌧ hc⌧ , h⌧ i  K q 1 + kck21:t 1.
Receive wt 2 Rd from Aunc; Receive yt 2 R from Aunc-1D. If t = 1, get hint ht Play xt = wt thtyt; Receive cost ct. Send ct to Aunc as tth cost; Send gt = thht, cti 2 R to Aunc-1D as tth cost.
end for
In this section, we consider unconstrained online learning in which the domain is all of Rd. In this setting, it is unreasonable to define the regret using a supremum over all comparison points u 2 Rd as this will invariably lead to infinite regret. Instead, we bound the regret as a function of u. For example, when hints are not available, standard results provide bounds of the form [7, 15, 28, 21, 5]:
TX
t=1
hct, xt ui  ✏+Akuk
vuut TX
t=1
kctk2 log(kukT/✏+ 1) +Bkuk log(kukT/✏+ 1), (7)
for constants A and B and any user-specified ✏. Using such algorithms as building blocks, we design an algorithm with O( p T ) expected query cost and for all comparators u, regret is Õ(kuk/↵).
The algorithm is somewhat simpler than in the constrained case: we take an ordinary algorithm that does not use hints and subtract the hints from its predictions. Intuitively, each subtraction decreases the regret by ↵kck2, so we need only O( p T ) such events. With constraints, this is untenable because subtracting the hint might violate the constraint, but there is no problem in the unconstrained setting. Instead, the primary difficulty is that we need the regret to decrease not by ↵kck2 but by ↵kukkck2 for some unknown kuk. This is accomplished by learning a scaling factor yt that is applied to the hints.
Moreover, in the case that all hints are guaranteed to be ↵-good, we devise a deterministic algorithm for the unconstrained setting. In light of Theorem 5.2, this establishes a surprising separation between the unconstrained and constrained settings. For the deterministic approach, we directly
measure the total query cost and simply query a hint whenever the cost is less than our desired budget. Note that this strategy fails if we allow bad hints as the adversary could provide a bad hint every time we ask for a hint. The full algorithm is presented in Algorithm 4, with the randomized and deterministic analyses provided by Theorems 6.1 and 6.2. Theorem 6.1. The randomized version of Algorithm 4 guarantees an expected regret at most:
2✏+ Õ
0 @ kuk p log(kukT/✏) h K + log(kukT/✏) log log(Tkuk/✏)K + pP t2B khtk2 log(T ) i
↵
1
A ,
with expected query cost at most 2K p kck21:T .
Theorem 6.2. If B = ;, then the deterministic version of Algorithm 4 guarantees: TX
t=1
hct, xt ui  2✏+O kuk p log(kukT/✏+ 1)
↵ + kuk log3/2(kukT/✏) log log(kukT/✏) K
! ,
with a query cost at most 2K p kck21:T .

heading: 7 Conclusions
text: In this paper, we consider OLO where an algorithm has query access to hints, in both the constrained and unconstrained settings. Surprisingly, we show that it is possible to obtain logarithmic expected regret by querying for hints at only O( p T ) time steps. Our work also demonstrates an intriguing separation between randomized and deterministic algorithms for constrained online learning. While our algorithms need to know ↵, an open question is to obtain an algorithm that can operate without knowing ↵. Extending our model to the bandit setting is also an interesting research direction.
Acknowledgments and Disclosure of Funding
Aditya Bhaskara acknowledges the support from NSF awards 2047288 and 2008688.

Review summaries:
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.

 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})$.

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.

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.