Logarithmic Regret from Sublinear Hints
Authors: Aditya Bhaskara
Ashok Cutkosky
Ravi Kumar
Manish Purohit
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online optimization
Full information
Regret bounds
Hints
Query cost

Abstract: We consider the online linear optimization problem, where at every step the algorithm plays a point $x_t$ in the unit ball, and suffers loss $\langle c_t, x_t \rangle$ for some cost vector $c_t$ that is then revealed to the algorithm. Recent work showed that if an algorithm  receives a _hint_ $h_t$ that has non-trivial correlation with $c_t$ before it plays $x_t$, then it can achieve a regret guarantee of $O(\log T)$, improving on the bound of $\Theta(\sqrt{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(\sqrt{T})$ hints under a natural query model; in contrast, we also show that $o(\sqrt{T})$ hints cannot guarantee better than $\Omega(\sqrt{T})$ regret. We give two applications of our result, to the well-studied setting of {\em optimistic} regret bounds, and to the problem of online learning with abstention. 

Logarithmic Regret from Sublinear Hints
Aditya Bhaskara
Ashok Cutkosky
Department Computer Science
Dept. Electrical and Computer Engineering Boston University
University of Utah Salt Lake City, UT
Boston, MA ashok@cutkoskky
bhaskaraaditya@gmail.com
Ravi Kumar
Manish Purohit
Google Research Mountain View, CA ravi wwwkkk53mmmm.....mmmmmmmkm..k.mm com
Google Research Mountain View, CA mpurohit@google.com
Abstract
We consider the online linear optimization problem, where at every step the algo- rithm plays a point Fę in the unit ball, and suffers loss (c, for some cost vector G that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint h, that has non-tri non-trivial correlation with c, before it plays 22, then it achieve regret guarantee of Ollog 7), improving on the bound of @(VT) in the standard setting. In this work, we study the question of whether an algorithm really requires hint at every time step. Somewhat surprisingly, algorithm obtain Ollog T' regret with just O(vT) hints under natural query model; in contrast, we also show that of o(vT) hints cannot guarantee better than (((T)) regret. We give two applications of our result, the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.
show that
Introduction
There has been spate of work 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 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 certain level of performance with poor quality or even adversarially bad hints.
Recall the standard online optimization model [30], which a game between an algorithm and an adversary. In each round, the algorithm plays point and the adversary responds with cost function that is visible the algorithm, and the cost 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 algorithm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

that plays 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 given round before it chooses a point to play at that round. In this sense, hints are present gratis [25].
The availability of hint in each round seems natural in some settings, e-g., when cost functions change gradually with time [25, 4J). However, it can be prohibitive in many others, for instance, if hints are obtained by using expensive side information, computationally expensive ML model. Furthermore, hints can also be wasteful when the problem instance, or even 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.
if they are generated by a running a
Our contributions. We now present a high level summary of our results. For ease of exposition, 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 e (and the cost or loss is the inner product of the point played with ce). 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 hint, there is efficient randomized algorithm that obtains Ollog T) regret using only O(vT) 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(VIB [ log T). while still asking for O ((VT) hints. It is interesting to contrast our result with prior work: Dekel et al. [8] obtained an algorithm with OlogT) regret, when a good hint is available in every round. Bhaskara et al. [2] made this result robust, obtaining a regret bound of O ((VBB /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(VT) 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 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 Olog 7') regret: we show that any (potentially randomized) algorithm that uses o( ((vT) hints will suffer regret of ((VT). The second and more surprising result is the role of randomness: we show that any deterministic algorithm that obtains Ollog T) regret must use / 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 deterministic algorithm to obtain 0(1og2/21) '') regret (suitably defined for the unconstrained case) when all hints are good, and a randomized algorithm to obtain Olog 7)) regret, which can be ex- tended 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 Ollog 7) regret using only 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(VT). 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 -VT total cost. However, if we simply play hint -he on ((VT rounds, each such round incurs -a cost, which is enough to cancel out the VT regret while making only O(VT) 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.
2

---

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.
Preliminaries
Let || denote the f2-norm and TB far TRd ||>||| S 1 denote the unit E ball in Rd. We use the compressed sum notation and use Ct denote > - C and |||| ia to denote E ||c Let č = c1...., Cr be a sequence of cost vectors. Let [T] = (1.....
OLO problem and Regret. The constrained online linear optimization (OLO) problem is modeled as a game over rounds. At each time t E [T], an algorithm A plays a vector 2, E IR and then an adversary responds with a cost vector G E 1 The algorithm incurs cost (or loss) (x,, ea) at time The total cost incurred by the algorithm is A = Σi= (Tz, ()). The regret of the algorithm A with respect to a 'comparator' or benchmark vector E Bd is
T
Ra(,, 2) cost A. (7)
Σ u, C.),
where A,, is the algorithm that always plays at every time step. The regret of an algorithm A is its worst-case regret with respect to all u E IBd;
(a(C) sup RA(u, C). WEB
Hints and query cost. Let >> be fixed and known. In this paper we consider the OLO setting where, at any round / before choosing Ir, an algorithm A is allowed to obtain a hint he E Bd. If (he, og) 2 alle 112, we say that the hint a-good. If A opts obtain hint at time then it incurs a query cost of allea112; 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 (-). The total query cost of A given by (c)
Ein 1 adfcce 1| where 1, is an indicator function used to denote whether A queried for hint time Note that the algorithm does not actually know the query cost for 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 h2 and cost vector at time 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 (ca, he) a:||ce|1: we let B denote the set of such indices t. Although assume is known to our algorithms, we do not assume any information about B. Further, our algorithm is charged |l||o=|12 2 for querying a hint even if the hint was bad.
3 Main algorithm
Intuition and outline. The high-level intuition behind our algorithm is the following: suppose for a moment that a = 1/2 and each hint is a-correlated with the corresponding cost. Now suppose the cost vectors cI,..., er 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 4vT steps, set steps, and play FTRL subsequently, then the cost incurred by the algorithm will be less than -2VT in the first 4 4 steps. and ( (in expectation) subsequently. On the other hand, for random vectors, we have || < 2/T with high probability, and thus the best vector in hindsight achieves total cost bost-Ilcr:r1) 2 22T.. Thus the algorithm above actually incurs regret < 0.
-h, in those
turns out that the key to the above argument is ||cr:|| being small. In fact, suppose that e are unit vectors, and assume that |||,T||| < T/4. Now, suppose the algorithm makes a hint query at 10vT random indices, sets I; -he in those steps, and uses FTRL in the other steps. One can show that the cost incurred by the algorithm is -5vT plus the cost of the FTRL steps. Since the cost in the
3

---

FTRL steps is within vT of the cost incurred by the competitor u, we can show that the regret is once again I The missing subtlety here is accounting for the cost on the query steps, but using the bound on ||c,-]|l this can be adequately controlled if the queries are done at random.
The above outline suggests that the difficult prior work of Huang et al. [11] showed that when the domain is the unit ball, FTL achieves logarith- mie regret if we have ||c|:]| || 2 Ott) for all t.
is ||crT|| || being large. However, it turns that
Our algorithm can be viewed as a combination of the two ideas above. If we could identify the largest round S for which |/c1:9l| is small, then can perform uniform sampling until round S and use FTL subsequently, and hope that we have logarithmic regret overall (although is not obvious that the two bounds compose). The problem with this is that do not know the value of S. We thus view the problem picking 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 certain time and 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).
3.1 A sharper analysis of FTRL
In this section we consider the classic adaptive Follow the Regularized Leader (FTRL) algorithm Ant (Algorithm 1) and show regret bound that is better than the usual one, if the length of the aggregate cost vector grows "rapidly" after certain initial period.
For convenience, let
||c||] Define the regularizer terms ro = and for t 2 1, let
v1 +0 01
V 01
(1)
By definition, have To: V + 1:t- Furthermore, have rr for all since a, ||ce112 1. The FTRL algorithm And then plays the points I T2, which are defined as
(CI.. 2) + Fost | |x1
Fe+1 argmin
|
Algorithm Adaptive FTRL Aud-
Algorithm 2 OGD with shrinking domain Augd-
31 0, To for 1- 1,..., T do
Require: Parameter À P1 f D1 < [0,
Play point 2t Receive cost Ce
for t = do
Play point Pt
To:
+ VI+ lcl..
Receive cost 24 and 0r S 1
Te+1 + argmin (CIn,) x) + To:t
||0]13]]
(o, will eventually be set to [|c.1²))
||
2
D. < [0, min(1, VI+oL. )]
end for
Ne 1t01e
Pt+1 +- IIp, (p. - =x)), where 1I is the
projection to the interval end for
We will show that Aut satisfies the following refined regret guarantee:
Theorem 3.1. Consider Agr on a sequence et of cost vectors and a E (0, 1) be any parameter. Suppose that S is an index such that for all > S, ||caall Z [1 + o1:)) (recall a; ||cel(2). Then,
1. For all N E [T] and for any ||u|| < 1, we have
Cr,, It - 4) S 4..5

---

2. For the index S defined above, we have the refined regret bound:
V1+0
+8 + 8 llog(1 + 01.)) ||cusl + Σ (z).
R.A (c)
(3)
2
Part (1) of the theorem follows from the standard analysis of FTRL; we include the proof in Ap- pendix B.1 for completeness. Part (2) is novel contribution, where we show that if |caall grows quickly enough, then the "subsequent" regret small. It can viewed as a generalization of result of Huang et al. [11], who proved such regret bound for 5 = 0.
3.2 Switch-once dynamic regret
In this section show regret bound against all time time-narying comparators of certain form. More formally, we consider the one-dimensional OLO problem where the costs are 2 and 2 1 is known parameter. We also assume that time the algorithm is provided with parameter de E [o, 1] that will give some extra information about the sequence of comparators of interest. Thus the modified OLO game can be described follows:
For t = 2..... the algorithm first plays pt E [o, 1]. and then 2,, og are revealed.
always satisfies =i S 40,,
We wish to minimize the regret with respect to a class of comparator sequences (4:)²= (defined below), i.e., minimize =p 2)) over all sequences in the class.
We remark that for the purposes this subsection, we can think of a as 27- (The more general setup is needed when use this in Algorithm 3.)
Definition 3.2 Walid-in-hindsighh sequences). We say that a sequence (4:) is valid in hindsight if there exists an S E [T'] and å E 1] such that
1. q: 8 for all S and q: for S. 2. At the switching point, we have 82 S 1+o.."
X²
We now show that a variant of online gradient descent (OGD) with a shrinking domain achieves low regret with respect to all valid-in in in-hindsight sequences; call this Auga (see Algorithm 2).
Theorem 3.3. Let 2 be given parameter, and (zt) 1 be any sequence of cost values satisfying Z < Aot Let (4: Ye be walid-in-hindsigge sequence. The points pt produced by Aogd then satisfy:
Σ
cpp: ạ:) S A(1+ 3log +1.T)) 1=1
3.3 Full algorithm
In this section we present the full algorithm that utilizes the above ingredients.
Algorithm Algorithm with hints Anints
Require: Parameter
Initialize an instance Aau and an instance of Augd with parameter À = 10/a
mat==1..... do
Receive pt from Angd: Receive & from And
With probability pt. get hint hy and play dt h4; otherwise, play di 3t
Receive c
Send e An as tth cost; Send 2, = -allec 1|2 (ce, and a. ||ce|12 2 to Aogd end for
Theorem 3.4. When B 0,
A (0) 78 38 log(1
||||| (.r) and E Am (6) s 20 /
a
5

---

Proof. Let us first bound the expected cost of querying the hints. From the description of Auga (Algorithm 2), because of the shrinking domain, we have 1
10
At time t,
the expected query cost paid by the algorithm is Pe |clll Using the above, we can bound this as
T pro |elll
T
10
T
10o,
&
& 20//1: = 20 Ie
VI+ +I+
Von
where the last inequality follows from concavity of the square root function (e.g., [20, Lemma 4)).
Now we proceed the more challenging task of bounding the expected regret. We start by noting that the expected loss on any round t is simply [e, 2t)] = (p, h4) +(1-p) Iz). Therefore the expected regret for a fixed is:
T
Σ Bllce, ât - = Σ pelce - he 21) + (ct, - u) S
Σ E=1
pe pa(=ailceel2 (ce, xz)) + (cr. - u),
t=1
where we have used the fact that the hint he a-good. The main claim is then the following.
Lemma 3,5. For the choice of Pr, 24 defined in Anian (Algorithm 3), we have
Σ pr(-allca12 (ce, (1), (0t, u) 78 38 log(1 + [elli.)) =0 0 (1+
log(1 + TI.T)
a
Assuming this, the bound expected regret easily follows, completing the proof.
We now focus on proving Lemma 3.5.
Proof of Lemma 3.5. The key idea is prove the existence of valid-in-hind -iinisgghth sequence (yx y (Definition 3.2) such that when on the LHS replaced with ft- the sum is (llo((T)/x The guarantee Algorithm 2 (i.e., Theorem 3.3) then completes the proof. Specifically, since we set 10/a and 2 (-alicell² - (cr, zz)), Theorem 3.3 guarantees that for any valid-in-hindsipe sequence (q:)== we have:
T
Σ pb (- (ct,xe)) + (ct, It u)
10
Σ a-aaalla,12 (c, xz), (c u) + a
(1 3 + [lc(2.))
(4)
Let us define S to be the largest index in [T] such that ||a.s| |l s [1 + 01.s). Firstly, by Theorem 3.1 (part 2), for any such index S we have:
T
cc. Es - u) V+ +
18 llg((1 + o1r) + ||cssl |I +
s Σ (1, t=1
Σ
(5)
2
a
Let A == VIoi + +||c + E (c., x.) denote the "excess" over the logarithmic term. Note that
by Theorem 3.1 (part 1), for a vector u = | we have |[c.s||| + S (c,,)) = E (
-61.8
u) S 4.5.I+++ T1.s. Thus, have < 5v1+o1..-
Now, note that if + 01.5 <
100 of we have 5 S 30/a. Thus, by setting 4: = for all t (which is clearly valid-in-hindsight, the proof follows. Further, if A 1, then clearly can again set de for all to complete the proof. Thus, we assume in the remainder of the proof that 1 + 01.s
100 and A 1. a²
Our goal now to construct a valid-in-hindsse -hindiihht switch-once sequence that has value g: 5 E [0, for < S and g: 0 for t > S such that we also have:
5
aσ; + (ce, (ct,
2 5VI+
(6)

---

First, let us understand the term in the parentheses on the LHS above. We bound this using the following claim.
Claim. a 01: + Eigsla, m.) 2 +oss).
Proof of claim. Suppose that have Eiss(er,
< 21 01:).. By definition of S, we have
VT+ 01: + ||c.:sll Σ (4, (1)
VI+o
(1 01:s) 2 0ss))
2
v 01:
a (1 + 0.s) +a.
2
From assumption that v 01.8 2 a the RHS above is a, which in turn is at most 1. Since we assumed A 1. this is a contradiction so the claim holds.
Thus in order to satisfy (6), we simply choose
10
av + f1.5
By assumption, this lies in [0, 1], and further, for À = 10/a, the (qt) defined above is a valid-in- hindsight sequence. Combining the fact that A < 5 01. with (6), we have that
T Σ q0 ad--alleel1 (ce, + (ct, Iz - u) 5
18 + log(1 (1 + 01.))
Now appealing to the guarantee of Theorem 3.3 as discussed earlier, we can replace di 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.
Extensions and applications
In the following subsections, we extend the analysis of Algorithm 3 to disparate settings: we con- sider robustness to uninformative or "bad" hints, the more classical "optimistic" regret setting, and online learning with abstention.
4.1
Bad hints
First, we extend Theorem 3.4 to consider the case B * 0 by carefully accounting for the regret incurred during rounds where L and making crucial use of the shrinking domain D,-
Theorem 4.1. For any B.
78 38 log(1 [ccl(2.)) + 40
20
E E a (2) x
Σ |c./ +
Σ :EB
lhel? log(11 + [|c]]?.r))
tE
v B log
and
E A
5 20
4.2
Optimistic bounds
Next, show that results have implications for optimistic regret bounds (e.g., [10, 6, 25, 27, 23]). The standard optimistic regret bound takes the form O(v Σ ||c, - 1.112). will show that the same result can obtained (up to logarithmic factors) even while only looking at O hints. The approach is very simple: if we set 7. then little calculation shows that for E B.
||c 2 + 2 Ollec h2ll?), so that Theorem 4.1 directly implies the desired result.

---

Theorem 4.2. Set a Then
A (0) 312 152 log(1 + [[lli:)) 80 1+ Vlog(1 + [|cl(ir))
Σ 1EB
ller he 1el2
= =0 (og(T))
Σ l hell bell))og(T)
and BlQ (7)) S 22000///0 /00/lelli.
4.3 Online learning with abstention
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 "abstain" any given round. When the learner abstains, it receives loss of -a]|e for some known but pays query cost of a/|ca.1.. 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] the expert setting, but in addition to moving from the simplex the unit ball, we ask for 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 works essentially out-of-the-boxx every time the algorithm queries 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 that abstains whenever the original algorithm would ask for a hint guarantees expected regret at most:
78 + 38 log(1 + [ccli.TT)
1 log(1 + HOiT)
Further, the expected query cost is at most 20 /elliT.
Proof. Since we abstain with probability Pt and otherwise play It. the expected regret is - -Pollclll + - (e,, (c,, u). Thus the regret bound follows directly from Lemma 3.5. The query cost bound follows the identical argument as Theorem 3.4.
5
Lower bounds
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 10 be any parameter, and suppose A an algorithm for OLO with hints hint queries. Then there exists a sequence of cost vectors 4 and hints by of unit
that makes I
length, such that (a) in any round where a hint is asked, (Ce, hx) 2 a @elcell", and (b) the regret of A on this input sequence is QV))).
Proof. We will construct distribution over inputs {c,, he) and argue that any deterministic al- gorithm has expected regret Q2 (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, he is chosen to be a uniformly random vector on the unit circle (in R²). The cost e is set to be oh, + v1 a² ht where hr is unit vector orthogonal to hęs and the sign is chosen uniformly at random. Now for any deterministic algorithm, if A queries h, time t, then it can play point ah, + b for scalars a, b. In expectation, this has inner product aa with Ct, and thus the expected cost incurred by A in this step is 2 -a (since lal < 1). If A does not query ht, then e is simply random unit vector, and thus the expected cost incurred by A in this step is 0.
Next, consider the value minjjulsi (e,,, u). i.e., the best cost in hindsight; this is clearly - 1 cell- By construction, is uniformly random vector the unit circle in I (and the

---

choices are independent for different t). Thus we have EIll,, cell 2 2(VT). (This follows from properties sums of independent random unit vectors; see Supplementary Material for proof.)
Thus, if the algorithm makes K queries, then the expected regret is at least - Ka (((T). This
quantity is ((VT) as long as K = o /T thus completing the proof.
We next show that for deterministic algorithms, making O(VT) hint queries is insufficient for ob- taining of v VT) regret, even if the hints provided always 1 1-good (i.e., hints perfect).
Theorem 5.2. Let A be any deterministic algorithm for OLO with hints that makes at most CVT < T/2 queries, for some parameter C O. Then there is sequence cost vectors er and hints he of unit length such that (a) h4 = Ct. whenever A makes a hint query, and (b) the regret of A on this input sequence is at least /T
2(1+C)
We remark that by setting appropriately, we can also show that for a deterministic algorithm to achieve logarithmic regret, it needs make Q log T queries.
Unconstrained setting
Algorithm 4 Algorithm with hints (unconstrained case).
Require:
Parameters K, d-dimensional unconstrained OLO algorithm Aunc, one-dimensional unconstrained OLO algorithm Amn-ID guarantecing (7) for f = 1,..., T do
{ [Randomized version] 1, < 1 with probability min (1, a a1titlllff....
K O otherwise.
(Deterministic version] } 1, < iff Σ (r(0,, K / ++||||l |
Receive w/ Rd from Ausc; Receive y R from Aunc-ID. If 11, = 1, get hint he Play 2, wt 1e Receive cost Ct- Send c to Aune as tth cost; Send yt -lee ct) E IR to Aune as ith cost.
end for
In this section, we consider unconstrained online learning in which the domain is all of R4, In this setting, is unrcasonable to define the regret using a supremum over all comparison points u Rd as this will invariably lead to infinite regret. Instead, we bound the regret function of u. For example, when hints are not available, standard results provide bounds of the form [7, 15, 28, 21, 5]:
Σ (0. s Allull
Σ ||..11 log([]u) 1) Bll |T/c 1),
for constants A and B and any user-specified Using such algorithms as building blocks, we design an algorithm with (VVT) expected query cost and for all comparators regret is Ó([u)l/a
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 a al|cc]] 1 so we need only O(VT) 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 al|c|| but by a |u||||/] for some unknown |/u]]- This is accomplished by learning scaling factor ye that is applied to the hints.
Moreover, in the case that all hints are guaranteed to be a-good, we devise deterministic algo- rithm for the unconstrained setting. light of Theorem 5.2, this establishes a surprising separation between the unconstrained and constrained settings. For the deterministic approach, directly

---

measure the total query cost and simply query a hint whenever the cost is less than our desired bud- get. 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 most:
2E + [Iully/og([|/]////
(
K
log([lu 2/c) log (og(T) + VEEB 11, log (T)
a
with expected query cost at most 2K Vlcl..
Theorem 6.2. If B = 0. then the deterministic version of Algorithm 4 guarantees:
T
| (I + log
l/2 3/2 (/) log log [u]
Σ
(c., 22 u) 2e +0
a
K
with query cost most 2K v /|elli.
7 Conclusions
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 obtain logarithmic expected regret by querying for hints only O(VT) time steps. Our work also demonstrates intriguing separation between randomized and deterministic algorithms for constrained online learning. While algorithms need know a, open question is to obtain algorithm that can operate without knowing a. 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.
References
[1] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In NeurlPS, 2020.
[2] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In ICMI., 2020.
[3] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online linear optimiza- tion with many hints. In NeurlPS, 2020.
[4] Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yo Yu Wei. Improved path-length regret bounds for bandits. In COLT, pages 508-528, 2019.
[5] Liyu Chen, Haipeng Luo, and Chen-Ya Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In COLT, 2021.
[6] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In COLT, pages 6-1, 2012.
[7] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In COLT, pages 1493-1529, 2018.
[8] Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with a hint. In NIPS, pages 5299-5308, 2017.
[9] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In ICML, pages 2319-2327, 2019.
10

---

[10] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by varia- tion costs. Machine Learning. 80(2-3):165-188, 2010.
[11] Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. JMLR, (8(145)1131, 2017.
[12] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In SPAA, pages 285- 294, 2021.
[13] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. ICALP, pages 69:1-69:18, 2020.
[14] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. JCSS, 71(3):291-37,, 2005.
[15] Michal Kempka, Wojciech Kotlowski, and Manfred K Warmuth. Adaptive scale-invariant online algorithms for learning linear models. In /CML, pages 3321-3330, 2019.
[16] Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. In ITCS, pages 50:1-50:20, 2019.
[17] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms using ML predictions. In NeurIPS, pages 9661-9670, 2018.
[18] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing. In ESA, pages 59:1-59:17, 2021.
[19] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In ICML, pages 3296-3308 2018.
[20] H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. JMLR, 18(1):11173316,, 2017.
[21] Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator norm adaptivity in on- line learning. In COLT, pages 2858-2887, 2020.
[22] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In ITCS, pages 14:1-14:18, 2020.
[23] Mehryar Mohri and Scott Yang. Accelerating online convex optimization via adaptive predic- tion. In AISTATS, pages 848-856, 2016.
[24] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In COLT, pages 3030-3048, 2020.
[25] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT, pages 993-1019, 2013.
[26] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, pages 1834-1845, 2020.
[27] Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In ICML, 2014.
[28] Dirk van der Hoeven. User-specifted local differential privacy in unconstrained adaptive online learning. In NeurlPS, pages 14080-14089, 2019.
[29] Chen-Ye Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In COLT, pages 1263-1291, 2018.
[30] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928-936, 2003.


Reviews:
[{"review_id": "e1c4sLAJCl", "reviewer": "Reviewer_6Hvo", "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})$.", "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": "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? \n\nAs 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {"ethical_concerns": "I don't see any ethical issues with this paper since the work is mostly theoretical. Perhaps the authors should consider the potential application of their work and if that may flag any ethical concerns.  "}}, {"review_id": "B9oB-XpfIy", "reviewer": "Reviewer_4B2U", "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.", "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": "- 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.\n- Quality: the paper is technical sound. Results are complete for the studied setting.\n- 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.\n- 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.\n\nSome questions:\n- Can the results be strengthened to high probability bound (on regret and the number of queries)?\n- 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}})$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretically and has no foreseeable societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "This work is purely theoretically and has no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "9fWnbNi4ML", "reviewer": "Reviewer_iLUL", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 is well-written. I have a few questions:\n\n1. 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. \n\n2. 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).\n\n3. 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?\n\nUltimately, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"ethical_concerns": "No problem here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "80xw7POlE2Y", "reviewer": "Reviewer_d9oi", "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.", "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": "Main strengths of the work:\n- 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.\n- The assumption that hints have limited availability is very well motivated in the paper via examples.\n- The proposed algorithm is relatively intuitive and it is easy to notice its novelties compared to prior works.\n\nMain drawbacks of the paper:\n- 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.\n- 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.\n- 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).\n- 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.\n- 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.\n\n****************\nPost-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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}]

Author rebuttal:

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)