Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper discusses the problem of online fair allocation under nonstationary data distributions. The authors describe the problem of fair item allocation at stake and the PACE algorithm they base their analysis on. Then, they derive several regret bounds under several types of nonstationarity, namely adversarial input, ergodic and periodic distributions. Then, they provide a summary of the proof techniques used to achieve these results.
strengths_and_weaknesses: The paper is well-written and introduces carefully the setup of the problem. Every assumption is justified and seems reasonable.
The resulting regret bounds are clear and provided with a quick interpretation.

The main issue of the paper comes from the empirical study: although the bounds are interesting, it would have been a preferable sanity-check to have toy experiments evidencing that the dependence in the ergodicity/TV-norm/etc.  reflects the true behavior of the regret. The proposed experiments are not in the main paper (and I believe that some results could be shortened/factorized to leave additional space in the main paper) and even the experiments provided in the supplementary materials are not very convincing. They show that PACE algorithm still holds under some nonstationary settings, but they fail to evidence the impact of increasing corruption/deviation from a stationary distribution, which is exactly what the theoretical results state. 
questions: In the original study of dual averaging for strongly convex objectives, Xiao et al. provided a method that could be sped-up with a surrogate function $h$, leading to a refined regret bound (at the cost of the introduction of a new hyperparameter $\beta_t$). Would such a function be conceivable in this case to improve the PACE performance?

Is there an intuition as to why a soft allocation will not lead to better rates for the PACE algorithm? Pure allocation does sound necessary in some settings but I wonder why a partial allocation could not be better if the setting allows it. Is it because we only care about expected regret here, and not about the variance?
limitations: The limitations of the different assumptions are clearly discussed throughout the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considered the problem of fair allocation of sequential items arrivals.  In particular, this paper extended the existing PACE algorithms, which requires i.i.d. item arrivals, to non-stationary cases.  To this end, this paper studied three non-stationary input models: adversarially-corrupted stochastic input, ergodic input, and block-independent input.  For each case, this paper presented new convergence results for PACE with dual averaging algorithm. Finally, numerical results are presented to validate the performance of the PACE against non-stationary inputs. 
strengths_and_weaknesses: Strength: 
- Generalization of the PACE to practical setting, i.e., non-stationary data.  This is critical and makes PACE more applicable in practice.  In particular, three non-stationary models are investigated. 
- Strong theoretical performance analysis:  For each of the non-stationary model, new convergence results are provided.  The convergence analysis for dual averaging under these three input models are novel and of independent interests.  This will benefit the community at large. 

Limitations:

The reviewer does not identify any major issues in this paper but has some minor comments that can be found below.

Overall, this paper is well written and relatively easy to follow, despite its very theoretical nature. The proposed new ideas and algorithms are clearly presented.  

- However, some good intuitions are missing in some parts for readers to better interpret the theoretical results, e.g., no discussions for Theorem 3 and Theorem 4. The paper seems to end unexpectedly after Theorem 4.  
- The background of the paper goes almost to page 5, which does not leave enough space to present and discuss the main results in the paper.  It may be better to make the background concise and some may be moved to the supplementary material.  
- The abstract mentioned the numerical results of the paper; however, the experiments are not presented, until the end of the supplementary material.   
questions: See limitations above. 
limitations: N.A.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper extends PACE [Gao et al 2021]  for online fair allocation to nonstationary settings. In particular, adversarially-corrupted stochastic, ergodic and periodic input are studied. Technically, this is done by using the connection of PACE with dual averaging (DA), and the new derivations of DA regret.
strengths_and_weaknesses: (+) This work extends PACE, which was designed for stochastic problems, to non-stationary settings.

(-) The online learning version of DA, aka follow the regularized leader (FTRL, see section 5 of https://arxiv.org/pdf/1909.05207.pdf) is capable of handling adversarial settings. Hence, it is not surprising that DA or PACE works for the nonstationary setting studied in this work. Can the authors discuss more on this? 
questions: Typo: line 112 "they they"
limitations: The main application domain is related to fairness.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: As I have notified the AC, this paper is certainly beyond my expertise. In addition, I’m not familiar with most paper in references. I'm simply making an educated guess.
strengths_and_weaknesses: From an outsider view, I think this paper is clearly written. 

The box around the reference is a little annoying, probably it is better to drop it.
questions: Is there any connection between the nonstationary setting in this paper and nonstationary reinforcement learning?

Ref:

Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach

Nonstationary reinforcement learning with linear function approximation

limitations: N/A
review_title: null

Meta-review: metareview: This paper studies the problem of online fair allocation. PACE algorithm has been proposed earlier to tackle this problem. Earlier analysis of this algorithm was under i.i.d. assumption. This paper presents a significant extension of the earlier work, providing guarantees for PACE under a significantly less restrictive data generating processes, e.g. adversarially-corrupted stochastic input, ergodic input, and block-independent (including periodic) input. This extension advances theoretical understanding of PACE algorithm and is of interest to Neurips community. The paper is recommended for acceptance.
confidence: Less certain
Decision: Accept