Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: For the setting of non-stochastic switching experts with memory, an explicit Mixing Past Posteriors formulation of the SOTA efficient algorithm is provided together with an improved regret bound, which also applies to relatively large number of switching experts. 
This is achieved by introducing an efficient projection-based algorithm for this setting and an efficient algorithm for computing projections onto an entry-wise lower-constrained simplex. The MPP equivalent of the proposed projection-based algorithm is shown to correspond to the (Bayesian) SOTA through a Bayesian interpretation.
main_review: The significance of the paper is mainly in introducing the first efficient MPP algorithm to match (actually improve) the state of the art regret bound for the setting of switching experts with memory. It also introduces an efficient algorithm for computing exact relative-entropy projections into entry-wise non-uniform lower-constrained simplex, that is then used as part of an new efficient projection-based algorithm for the setting, achieving (actually improving) the SOTA regret bound. The paper also suggests (Theorem 4) the advantage of the projections-based algorithm over the MPP variant for settings with switching costs.

The presentation of the material is clear and the paper is easy to follow. Relevant references are provided and the contributions of the paper over the state of the art and related results from relevant domains are explicitly stated. I do have a couple of comments/questions nevertheless:

1) To assess the significance of the improvement in the regret bound (the discussion around line 250) it would be helpful to also refer to a relevant lower bound on the achievable regret.
2) The way I see the flow of ideas in the paper, it is first established that for a projections-based algorithm to be efficient two elements are needed - an efficient computation of the projection, and an efficient computation of $\beta_i$ (line 176). The paper then proceeds to implement an efficient projections-based scheme, and its (efficient) MPP equivalent (section 4) having an explicit formulation of the $\gamma$ updates. My question is going back to (12), and comparing it to the PoDS-$\theta$ rule (15).  This should 'close the loop' in  a sense, providing an efficient formulation of a solution to (12) (which is impossible in general) for the structure introduced by the  PoDS-$\theta$ algorithm, and using the explicit form of (20).

Finally, a few suggestions/typos: 
Typo: replace $v_i$ in line 67.
Clarify what is meant by "absolute loss" in line 70.
Should be $\ln nT$ in line 79.
Include $k=40$ in the plot of Figure 1, not only at the caption.
 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The setting in the paper is the one of prediction with expert advice in a non-stationary environment - the learner competes against a sequence of switching experts [This setting was introduced by Bousquet and Warmuth, 2002].
The authors propose an algorithm that improves upon previously known regret bounds.
The main novelty is incorporating a relative entropy projection step onto a simplex. This projection step can be computed in linear time (of the number of experts).
main_review: Significance: The paper discusses fundamental questions in Online Learning. 
The suggested algorithm improves upon previous results while introducing new techniques that seem to be useful in other contexts as well.

Clarity and relation to prior work: The paper is very clear and easy to follow. 
The authors described thoroughly previous results and their connection to their paper.

Question: who is H in (3) and (9)?

limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a specific setting for the online expert tracking problem: the expert comparison sequence consists of a few unique experts relative to the number of switches. 
In order to solve this problem, the author/s proposes new algorithm to keep track of the lower box constraints \beta (the similar fixed share parameter for the non-projection variant) for each expert with Markov chain update. To solve the lower box constraint projection, it also proposes a O(n)-time per trial projection-based algorithm for the n experts. All the proposed algorithms are based on prior works on the same problem setup.
The performance guarantee of the proposed algorithm could further improve the current best-known efficient algorithm by a constant number.
main_review: The paper is well-written and easy to read. The main concerns I have are about originality and result' significance.

1. The contribution for the linear-time projection algorithm 3. As the paper points out, it is based on the prior work when the box constraint lower bound is universal over different experts. But for this paper's algorithm, it needs to have different lower bounds for different experts. Algorithm 3 modifies the prior work and solve this problem. But the difficulty of it is debatable. Also, I don't see any new insights from Algorithm 3 as well.

2. The contribution for the Algorithm 1&2. As pointed out in the paper, this algorithm is based on prior works ideas in Eq.(12) and the partition specialists Markov chain update in [26]. The update rule in Algorithm 1&2 step 9 seems to be from the [26]'s Markov chain update and just generalizes the chain update. Because the original inefficient algorithm from [4] has the observations of Eq.(12) (which is the kind of box constraint projection), and the follow-up work [26] proposed an efficient algorithm with the Markov chain update (which is the Markov chain update rule idea for Algorithm 1&2 step 9). Based on the above arguments, there is no surprise that the algorithm 1&2 could have a mixing scheme MPP explanation in Section 4.

3. The comparison in Figure 1 is unfair. For the result in this paper, it depends on the tuning parameters m (the number of unique experts) and the k (the number of switches). And this paper's result in Figure 1 depends on this prior knowledge, while the prior work [26] does not need such information, which explains the reason to have increasing values for MPP and Partition Specialists. In other words, this paper's claim on having better theoretical results out of the range m<<k is not accurate. If we only consider the m<<k case, the theoretical improvement is really minimal, only a constant term improvement.

=========== After rebuttal ================
Thanks the author/s for the detailed explanation on my initial reviews.

After checking the work [26] more carefully, I agree with the author/s that the comparison in Figure 1 is fair.

However, for Algorithm 3's contribution on the efficient linear-time projection, I am not convinced that its contribution is significant enough given the prior work's efficient algorithm.

For my second concern on Algorithm 1&2 and the reply from the author/s, I totally agree that Algorithm 1&2 are not directly from [26]. Although we could put the correspondence between P (P_ww, P_ws, P_sw, P_ss) from [26] and \theta, \alpha from this paper, and we will at least achieve the performance guarantee from [26], the paper's contribution about the revelation of the Markov prior over partition specialists corresponding to a geometrically-decaying mixing scheme is not trivial.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: Following our discussion, the reviewers and I all agree that this is a well-written paper that makes a solid contribution (albeit on a somewhat niche problem) and the techniques are interesting and would be of interest to the community.  I encourage the authors to further clarify the relation to prior work in their final version, in terms of improvements and techniques, paying particular attention to comments by Reviewer i3gM.

Decision: Accept (Poster)