Despite an ever growing literature on reinforcement learning algorithms and applications, much less is known about their statistical inference. In this paper, we investigate the large-sample behaviors of the Q-value estimates with closed-form characterizations of the asymptotic variances. This allows us to efficiently construct confidence regions for Q-value and optimal value functions, and to develop policies to minimize their estimation errors. This also leads to a policy exploration strategy that relies on estimating the relative discrepancies among the Q estimates. Numerical experiments show superior performances of our exploration strategy than other benchmark approaches.
This paper studies the asymptotic properties of action value function $Q$ and value function $V$. Specifically, the authors assume that we can collect $n$ data points $\{(s_t,a_t,r_t(s_t,a_t),s_{t+1})\}_{t=1}^{n}$. Based on the collected data, the authors calculated the sample mean of the unknown reward function $\widehat r_n$ and transition probability $\widehat{P}(\cdot|s,a)$. They further defined an estimator $\widehat Q_n$, which is the fixed point of the empirical Bellman operator $\widehat{\mathcal{T}}_n$ derived from $\widehat r_n$ and $\widehat P_n$. The authors proved under certain assumptions that $\widehat Q_n\rightarrow Q^*$ almost surely. Based on this argument, they also derived a similar convergence of value function $\widehat V_n$ in distribution. Confidence intervals can also be established based on these results.
The proof of convergence in distribution is established based on the following idea: $\widehat r_n$ and $\widehat P_n$ converge to $r$ and $P$ by central limit theorem. By examining the Jacobian matrix of $\widehat{\mathcal{T}}_n$ with respect to $\widehat Q$, it is found that the implicit function $\widehat{ \mathcal{T}}_n \widehat Q -\widehat Q=0$ can be solved in small neighborhoods of $\widehat r_n, \widehat P_n$ and $\widehat Q_n$ as
$$
\widehat{Q}_n = \phi(\widehat{r}_n, \widehat P_n) \qquad\text{(implicit function theorem)}
$$  
Then by Slutsky theorem, $\widehat Q_n = \phi(\widehat r_n, \widehat P_n)$ also converges to $Q^*$ in distribution. The proof is straightforward and easy to follow. However, I have some concerns about the above analysis.
1. The data $\{(s_t,a_t,r_t(s_t,a_t),s_{t+1})\}_{t=1}^{n}$ are collected by executing a fixed policy for n steps, which means the data points are not i.i.d. Therefore, the convergence of  $\widehat r_n$ and $\widehat P_n$ by central limit theorem may not hold ground, which further leads the later proofs potentially problematic.
2. The $\phi(\cdot,\cdot)$ function in implicit function theorem only exists in neighborhoods of $\widehat r_n, \widehat P_n$ and $\widehat Q_n$. It is unclear from the current proof that $\widehat Q_n$ fall into the same neighborhood of $Q^*$. Therefore, it needs to be justified that the limit point is $Q^*$.
3. Even for the empirical estimator $\widehat Q_n$, it is still the fixed point of $\widehat{ \mathcal{T}}_n$, which is hard to compute or solve. Thus Algorithm 1 may be inefficient in practice.
Other comments:
The font and margin of this paper does not conform the format requirement of ICLR.
What is $\sigma_R(i,j)$ in Theorem 1 and Corollary 1? It seems to be undefined.
I found it hard to read when the authors vectorize all the matrices and tensors to $N$ dimension vectors and $N\times N$ matrices. In particular, the rearranged notations such $\mu((i-1)m_a+j)$, $\tilde P^{\pi}((i-1)m_a+j,(i’-1)m_a+j’)$ are much more complicated that $\mu(i,j)$ and $\tilde P^{\pi}(i’,j’|i,j)$. Similarly, the mapping $F(Q’,r’,P’)$ defined in the proof of Theorem 1 can be represented by the Bellman operator $\mathcal{T}$ defined on page 3. 
====post rebuttal==
I read other reviewers' comments and the author's response. I do not think the authors have addressed all my concerns. I will keep my rating.