Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the prediction problem for Markov chain with more than $3$ states, and without the spectral gap.
main_review: Strengths:

1. This paper proves the optimal prediction risk with the number of states between 3 and $\sqrt{n}$ without the spectral gap, which requires more difficult proof technique than previous works analyzing markov chain with 2 states or with spectral gap.

2. To achieve optimality, the paper defines an average of add-on estimators to be a new estimator and proves its optimality. 

3. The role of spectral gap is characterized clearly in the prediction risk. 

Weakness / comments: 

1. The most natural estimator for $M(j|i)$ might be the empirical frequency $N_{ij}/N_i$ instead of the add-one estimator in (5). It might be beneficial to discuss the reason why you use the add-one estimator: is it because empirical frequency is sub-optimal in nature, or just a technical issue.

2. The structure of this paper is a little strange. It might be better to move the main theorems and proof techniques (Section 1.1) outside the introduction (Section 1).
limitations_and_societal_impact: This is a theoretical paper, and I think there is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the following problem: given data from a stationary Markov chain with discrete support, can we learn the stationary distribution? It derives the optimal rates for this learning problem when the spectral gap of the Markov chain is arbitrarily slow, and shows that when the spectral gap is bounded below, one can achieve parametric rates.
main_review: The paper studies a clear and well motivated problem, and introduces universal compression techniques to the study of Markov chains. The result for Markov chains without spectral gap assumptions is nice.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: From a single trajectory of $n$ observations drawn from a Markov chain over $k$ different states, we are interested in predicting the next one.
For some notion of risk they define, the authors prove that when $k \geq 3$,
the rate is of the order $\Theta((k^2/n) \log (n/k))$.
In particular, this shows the surprising fact that this rate has a different (worse) dependence in $n$ than chains over $k = 2$ states, known to be $\Theta((1/n)\log \log n)$.
Furthermore, they analyze the minimax problem over the set of chains whose spectral gap is controlled from below, and
show that under favorable (quantified) mixing conditions, one even recovers the "iid parametric" rate $\Theta(k^2/n)$.
main_review: The paper is very-well written, and offers strong results. The problem is hard, and was until now only understood for the restricted 2-state case. The bounds are matching up to universal constants. The techniques are involved, enabling the authors to obtain bounds that are independent of the mixing properties of the chain (Th.1).
Although this reviewer did not verify the proofs carefully, they have found no reason to doubt them. This is a strong submission; this reviewer recommends acceptance.

* (L31-L38;L186-192)
In these two paragraphs, the authors seem to imply that there is something inherently simpler about the prediction problem than, say, estimation, illustrating this by saying that consistent estimation of the transition kernel is not possible if the stationary distribution comprises extremely small values. This last part, however, is a bit misleading and depends on the notion of distance one considers.  
It is true that some notions of distance lead to a minimax rate that also captures a dependence in the stationary distribution.
But for example, by weighing the state-wise discrepancy in terms of the stationary distribution as in Hao et al. [2018, p.2], or considering a distance in terms of the edge-measures of the chains as  in Wolfer and  Kontorovich  [2021,  Theorem  3.3], it is possible to obtain rates that are independent on the stationary distribution for the estimation problem.

* (L79-81) Note that such interesting decoupling has also been observed in the Markov chain testing literature for some notion of distance (cited by the authors).

* Add a few words on algorithmic complexity.

* On page 1, when taking the infimum, indicate whether estimators must be (proper) Markov kernels.

* Since the results are expressed up to universal constants, one can remove squares from the logs in the bounds $\log (1 / k^2) = C \log 1/k$.

**REFERENCES**

* Y. Hao, A. Orlitsky, and V. Pichapati. On learning markov chains. In NeurIPS, 2018.  

* Wolfer  and  A.  Kontorovich.    Statistical  estimation  of  ergodic  markov  chain  kernel  over  discrete  space. Bernoulli, 27(1):532–553, 02 2021.  doi:  10.3150/20-BEJ1248.
limitations_and_societal_impact: Addressed adequately.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: Applying techniques from universal compression, the authors characterize the optimal prediction risk in KL-divergence of the following problem: Based on a trajectory of length $n$ drawn from an unknown Markov chain with a state space of size $3\leq k\leq O(\sqrt{n})$, predict the next state.
main_review: The paper is of high quality and the results are significant and interesting. Nevertheless, while the authors do make efforts to explain their ideas and machinery, I find that the paper is hard to read and that several points are not clear or confusing. For example, even after several reads I am not sure what "with and without spectral gap" means. Does it mean with and without ASSUMPTIONS on the spectral gap? Section 3 is called Optimal rates without spectral gap but there is no corresponding section for "with". Furthermore, Section 3 is concerned merely with the lower bound. Additionally, in Section 2 there are results that make assumptions on the spectral gap and results that do not.

Adding to the confusion, the connection between subsequent paragraphs is sometimes not clear and sometimes explanations for results come AFTER they appear. This makes reading difficult and hard to understand what exactly wad done by the authors and what is already known.

I would also make the following specific suggestions. Whenever my remark is formulated as a question I mean that I find that an explanation IN THE TEXT is necessary.

1. [line 25] While it can be assumed that if $Y\sim P$ then $p_{i}=P(Y=i)$ and similarly for $Q$, this should be made clear.
2. [lines 36-38] I am not sure about the correctness of the claim that “if certain state has very small probability under the stationary distribution, consistent estimation of the transition matrix may not be possible”. Under irreducibility, every state is visited infinitely many times and consistent estimation is guaranteed. Under reducibility, some states may not be visited at all and the corresponding transition probabilities cannot be estimated.
3. [lines 50-51] Since highly related to this work, the authors should clarify what exactly “implicit assumptions on mixing time such as spectral gap conditions” that were made by HOP18 meant. (or at least point to where they are stated in HOP18, since I have not found them there).
4. [line 53] The authors should make the phrase “with and without spectral gap” more precise. Isn't “without assumptions on the spectral gap“ or “arbitrary spectral gap” clearer?
5. [line 87] It would be informative to explain the sudden restriction to reversible Markov chains. Is it an artifact of the analysis? Do reversibilization methods fail? What about the pseudo spectral gap?
6. [lines 92-93] From $\gamma_{0}>0$ it follows that the Markov chain is aperiodic. Together with irreducibility this give ergodicity. The authors might want to use this term explicitly.
7. [line 96] In what sense is Theorem 2 an extension of (2) of [FOPS16]?
6. [lines 124 and 131] “known as redundancy” and “is standard”. The authors might want to give references for the definition and for the result.
8. [line 142] To which reduction do the authors refer?
9. [line 213] Is there a reason for $X^{n+1}$ instead of $X^{n}$? What is $\Theta$?
10. [line 214] Shouldn't the definition $X^{n}\overset{\Delta}{=}(X_{1},\ldots,X_{n})$ come before line 213? Actually, $X^{n}$ was already defined in line 23.
11. [line 220] Here a more exact reference is given ([CT06, Chapter 13]). It would be nice if the authors could provide exact references for the well known definitions and results that are being used.
limitations_and_societal_impact: I don't see any potential negative societal impact.
I suggest formulating the theorems in a more detailed manner that makes the assumptions made explicit.
review_title: null

Meta-review: This paper is interested in predicting the next state, given $n$ observations from a single trajectory of a Markov chain. It is very well-written and offers strong, significant, interesting results.
Decision: Accept (Poster)