Online Learning with Sublinear Best-Action Queries

Summary

In this paper, the authors studies the classical problem of online learning in the additional context of algorithms with predictions, or learning-augmented algorithms. In online learning, a learning algorithm must repeatedly select from a set of options, each associated with a loss function, and the goal is to minimize the regret, i.e., the difference between the (expected) loss of the algorithm and that of the best fixed option in hindsight. The loss function may be adversarially generated based on time and prior actions, which makes obtaining good regret traditionally hard. By utilizing predictions to give the learning algorithm some additional information about the unknown loss function, we may be able to obtain better regrets and break impossibility bounds. The authors incorporate 'best-action queries', which are queries that informs the algorithm the best option at the current time step. Prior work considers different form of predictions or queries, such as a vector correlated with the actual loss function, or the best option amongst a small subset of all the options. This work differs from prior works both in the form of the advice, and that the learning algorithm is only allowed to query at $k$ out of $T$ time steps. WIthin this advice model, the authors show that in either the full feedback model, in which the full loss function is revealed to the algorithm after every time step, or the label efficient feedback model, in which the algorithm is only given the full loss function if it issues a query in the current round, the query budget $k$ multiplicatively affects (decreases) regret. This is a surprising result since the regret per round is upper bounded by $1$, so $k$ rounds can only increment the regret additively instead of multiplicatively. The algorithm the authors propose is a very simple and intuitive modification of the classical Hedge, or multiplicative weights, algorithm, except that in $k$ out of $T$ rounds, randomly sampled according to some procedure, the algorithm queries the best-action and follows it instead of a weighted selection amongst all options.

Strengths

The paper studies the intersection between two interesting fields, learning-augmented algorithms and online learning, and contributes positively to its literature. Traditionally, the field of learning-augmented algorithms places a focus on (classical) online algorithms, so whether external predictions can help online learning is a very natural extensional question to ask. Over prior works in the same intersection, the authors additionally showcase the power of such predictions by showing that a small number of queries or predictions can significantly decrease the loss/regret of online learning algorithms, which is a very surprising and exciting discovery.

Weaknesses

I find the author's presentation somewhat rushed and unsatisfactory, and makes significant assumptions on the reader's background knowledge. Coming from a learning-augmented algorithm background, I find many online learning aspects of the paper not sufficiently defined or explained in a self-contained way, despite having some familiarity with the field. Some minor points of complaint are listed in the Questions section below. More importantly, a majority of the main corpus of the paper consists of technical proofs following one another, without much introduction or intuition in between to give the readers a high-level guideline of what is going on in the paper. It is very hard, without full familiarity of relevant literature, to follow the author's proofs, and understand what part a claim or statement plays in the grand scheme of proving the main theorems. As a result, while I believe the author's claims are overall correct, I am unable to confidently confirm the technical soundness of the paper. Overall I still believe that this is an exciting paper; but its presentation can be improved significantly.

Questions

The authors discuss the potential of using noisy, possibly erroneous predictions or queries in the conclusion. From my understanding, the learning-augmented algorithms community put a lot of emphasis on utilizing machine-learned oracles that can possibly be accurate but have no rigorous guarantees to facilitate and *augment* classical algorithms to retain both *consistency* (good performance when predictions are accurate) and *robustness* (good performance even when predictions are arbitrarily bad). As a result, I would be very interested in seeing discussions and extensions in this noisy prediction regime in the future. As illustrated above, I believe that a lot of intuition, such as high-level description of the proof strategy, and the usage and purpose of each component lemma or claim in colloquial terms, would be very helpful to the overall presentation in the main corpus, and can help guide readers to follow the flow of logic. Some minor details I would like to point out: - Line 35-36: "... the platform's task **consists in** deciding whether..." should be "consists of"? - Line 49: "...with full feedback, **an** in the **stochastich** multi-armed...". - The phrases "loss" and "feedback" are both used a lot, perhaps interchangeably, which is somewhat confusing. This is especially important in the label-efficient feedback section, in which it is not immediately clear what is "partial" about the "partial feedback" given to the algorithm. Is it just that the algorithm receives the loss function only when it makes a query, or is the received loss function itself partial? - Line 102-103: The entire sentence within the parenthesis does not make sense to me, grammatically. - Line 120: The introduction contains multiple mentions of the classical Hedge algorithm, but never explains, in any level of detail, what is the Hedge algorithm. From their pseudocode of Algorithm 1, which is described as a modification of Hedge, I can extrapolate that Hedge is the classical multiplicative weight algorithm, but the authors did not even make this clear in the introduction. - Line 142: "We have the following theorem." Which theorem is this sentence exactly referencing to? Theorem 2.2 is the natural candidate but its statement predates this sentence. - Line 162: I find it somewhat slightly strange that of the two algorithms presented in the paper, one is given a pseudocode block, while the other is only given a description. - Line 196: "...we construct two **of** randomized instances...". - Line 199-200: "(and $Z_t$ is an empty $n$-dimensional vector)". Is the scope of this sentence if a query is not issued at time $t$?

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors sufficiently discuss limitations and future directions in the conclusion section. There are no ethical concerns or limitations in their work.

Summary

The paper’s title concisely summarizes the topic. They study both the “full feedback” setting, where the learner observes the entire loss vector (what the loss would have been for each possible action) on each time step, and the “label-efficient feedback” setting, where the learner only observes the loss vector on time steps when a query is issued. The results are as follows: 1. An algorithm for the full feedback setting which achieves regret $O(\min(\sqrt{T}, T/k))$ with k best action queries. Interestingly, the queries are issued uniformly at random. 2. An algorithm for the label-efficient feedback setting which achieves regret $O(\min(T/\sqrt{k}, T^2/k^2))$. The queries are also issued mostly at random here (specifically, uniformly at random until the budget is exhausted). 3. Lower bounds for both of the above results which are asymptotically tight.

Strengths

I find the model of sublinear best-action queries to be quite natural, and the authors also do a good job of motivating it. One example given in the paper which I found compelling was an algorithm for flagging harmful content which can escalate to a human review a limited number of times. I also found the results to be impressive. As the authors state, > Note, the total of the losses incurred by any algorithm in k rounds is at most k, which only affects the overall regret in an additive way; nevertheless, we prove that issuing k queries has an impact on the regret that is multiplicative in k. This seems like a potentially powerful insight to me.

Weaknesses

I found the paper to be quite technically dense. Although the description of the results in the introduction was clear, the authors don’t provide much intuition for their results. I had a hard time identifying where (on a technical level) the multiplicative power of k comes from. Conveying technical intuition along with technical results is very beneficial for other researchers trying to make use of the insights from this paper. I suspect the impact of the current version of paper is limited by the presentation. For transparency, I will mention that I am not an expert in this sub-area, and it is possible that experts would not have the same complaint. However, to the extent that the intended audience of this paper is researchers in related but not identical fields, I think this weakness is significant. See also the “limitations” section below.

Questions

Can you provide technical intuition for where the multiplicative power of the best-action comes from? Below are minor comments that the authors are free to use or discard. I’m including them in this section because I don’t know where else to put them, but I don’t expect responses. - Line 71: “In our paper we pinpoint the exact minimax regret rates for the problems studied.” It might be worth saying “asymptotically tight” instead of “exact” (although it’s pretty clear from context). - Lines 84 - 86 are quite compelling. - Line 93: Maybe mention that the learner still observes the entire loss vector, not just the best action. - Lines 132 - 133: “combining the Hedge algorithm [Chapter 2 in Cesa-Bianchi and Lugosi, 133 2006] to uniform queries” → “with uniform queries”? - Line 200: “and Z_t is an empty n-dimensional vector” → “and Z_t is an empty n-dimensional vector otherwise”?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

In Question 2 of the checklist, the authors state: > The paper has no significant limitation. Being theoretical in nature, there is a set of model assumptions I found this answer to be disappointing. Theoretical papers absolutely have limitations. Are the model assumptions realistic? If not, to what extent do the results crucially hinge on those assumptions? Do the algorithms have inefficiencies that would impede or preclude practical usage? Are the technical insights too complex to be easily understandable by other researchers? These are just example limitations; I’m not claiming that any of these particular examples apply to this paper.

Summary

This paper considers an online learning with actions model where the learner is allowed to make $k$ "best action queries". Such a query at step $t \in [T]$ will return $i_t^\ast \in \arg\min_{i \in [n]} \ell_t(i)$; an action that minimizes the loss at step $t$. The loss values are bounded (in $[0, 1]$ w.l.o.g) and may be generated by an oblivious adversary. The best action query is performed _before_ the learner makes the decision (arm choice). The regret of the learming algorithm is defined in the usual way. They first consider the full feedback setting, where _after_ making the arm choice, the learner observes the entire loss vector $(\ell_t(1),\ldots,\ell_t(n))$. In this setting, without best action queries, the Hedge algorithm gives $\tilde{O}(\sqrt{T})$ regret for bounded losses (and this is well-known to be optimal). (i) In the full feedback setting (augmented with best action queries), the authors show that the Hedge algorithm with $k$ uniformly random best action queries gives an (expected) regret of $\tilde{O}\left(min\\{\sqrt{T},T/k\\}\right)$. This beats the standard regret bound when $k$ is $\omega(\sqrt{T})$. (ii) They also show a matching lower bound (up to $\log n$ factors) that any full-feedback algorithm with $k$ best action queries (not necessarily random) will suffer $\Omega(\sqrt{T},T/k)$ (expected) regret. They then consider a label-efficient feedback model w.r.t the best action queries. Here the restriction in feedback is entirely in terms of observing the loss values (there is no outcome space) and linked to the best action queries themselves. The learner can make $k$ best action queries; if the learner chooses to make a query at time step $t$, it receives the full feedback after it makes the choice. Otherwise, it receives no feedback. (i) In the label-efficient feedback setting (augmented with best action queries), the authors show that the label-efficient Hedge algorithm (does not update the probabilities when there is no feedback) with random best action queries ($\leq k$ of them, but not quite uniform random unlike in full feedback) achieves $O\left(\min(T/\sqrt{k},T^2/k^2)\right)$ regret. This beats the known regret bound for label-efficient Hedge (from Cesa-Bianchi and Lugosi 2006) when $k$ is $\omega(T^{2/3})$. (ii) They also show a matching lower bound for regret (up to $\log n$ factors) of any algorithm with $k$ query label efficient feedback. In the appendix, they show nearly identical bounds for full feedback and label-efficient feedback in the stochastic losses setting. Here the algorithms are Follow the leader and Explore then commit, and the best action queries are simply made in the first $k$ rounds.

Strengths

* The model (best action queries) is theoretically interesting and the results are quite nice in the sense that you can get polynomial improvements in the regret by incorporating _sublinearly-many random_ best action queries with the standard (full feedback and label efficient feedback) Hedge algorithms. * The paper is well-written. Almost all the proofs are cleanly presented in the main matter itself. They also survey and compare some of the existing work on augmenting online prediction algorithms with additional information.

Weaknesses

* Even though the best action query model yields theoretically interesting results, it is a bit too strong compared to some of the existing work. Even if only sublinearly many queries are made, each query is supposed to give the _correct best action (among all)_ for that time step before making the decision, and the number of queries needed is still polynomial in $T$ (at least $T^{1/2}$) to get any interesting result w.r.t the regret (in both full feedback and label efficient feedback). When the authors link best action queries to human expert advice in the introduction section, the assumption on the queries becomes somewhat impracticable.

Questions

* In the equations after line 178, is the last equality an inequality ($\leq$) using $T\eta \leq \hat{k}$?

Rating

5

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

* There is no negative social impact. * The major practical limitation is the strong requirements of the query model. It would be much more feasible if (i) the queries returned an "approximate" best action among all, (ii) the queries returned the exact best action among a subset of actions or (iii) interesting results were obtainable with logarithmically many queries.

Summary

This paper considers the standard prediction with expert advice setting of online learning, but with the twist that the learner may issue, up to $k$ times, a "best-action query" before making a prediction, in which case the identity of an expert incurring the smallest loss in the round is revealed to the learner (and of course they can choose that expert on that round). Two settings are investigated: the standard experts setup wherein the losses of all experts are revealed after each round, and the 'label-efficient prediction' (LEP) setting, where the losses are not revealed unless the learner issues a query for the same (which the authors identify with the best-action query, i.e., all losses are only revealed when the learner makes a best-action query). The paper shows that these $k \ll T$ best-action queries have an impressive effect, improving the regret in the experts setting to $O(\min(\sqrt{T}, T/k)$, and in the LEP setting to $O(\min(T/\sqrt{k}, T^2/k^2)$. Surprisingly, the method achieving this is just hedge, but run with losses of the form $\ell_{t,i} - \min_i \ell_{t,i}$ instead of just $\ell_{t,i}$ (and the appropriate modification a la prior work on LEP for this setting). The approach to showing this uses the standard analysis of the hedge algorithm, and uses the additive advantage of the best-action queries to allow the method to set an aggressively large learning rate (when $k$ is large enough) without suffering a strong penalty for the same, leading to improved regret bounds. The paper concludes by showing matching lower bounds for this setup, in a minimax sense.

Strengths

I think that this paper is both pertinent and timely: the investigation of how augmented information can improve regret in classical online learning settings has been an interesting direction of research in the recent years, and the paper makes a significant contribution to this body of work. I particularly find the improvement in the LEP setting to be remarkable. The paper is further well written and easy to understand, with existing arguments being used in an interesting new way.

Weaknesses

I don't see major weaknesses in the paper. I think the only change that is necessary is that the discussion of the related work in section C should be moved to the main paper, since this provides valuable context to the investigation presented within (but this should be easily accommodated with the extra page, if the paper is accepted). Perhaps another point of improvement lies in deepening the discussion of scenarios where the model being studied has pertinence. The moderation setup certainly is interesting and natural, but are there other situations where the authors see the relevance of best-action queries?

Questions

Suggestion: One approach to modeling problems like using limited moderation effectively that I have seen is through the abstention model of learning, wherein the learner may "abstain" on a query, and receive a "best-response" by utilising extra resources. I think work on online abstention may thus be a useful point of contact with the literature that the paper misses, and might be worth including a discussion on. This includes both the KWIK model, and the full-information model. Useful points of contact with this literature are below. Li, Littman, Walsh, and Strehl, Machine Learning 2011, Sayedi, Zadimoghaddam, and Blum NIPS10; Zhang and Chowdhuri, COLT 16; Cortes et al., ICML 18; Neu and Zhivotovskiy, COLT 20; Gangrade et al., Neurips 21

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

This is fine