Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors develop a new algorithm for linear bandits that achieves a uniform-PAC bound of $\tilde{O}(d^2/\epsilon^2)$, meaning that for all $\epsilon > 0$, the algorithm outputs an action whose suboptimality is at most $\epsilon$ after $\tilde{O}(d^2/\epsilon^2)$ rounds of iterations. The authors further generalize their techniques to linear MDPs and develop an algorithm that achieves a uniform-PAC bound of $\tilde{O}(d^3H^5/\epsilon^2)$.
main_review: Uniform-PAC is a notion developed by Dann et al. [8], which says that with probability at least $1-\delta$, for any $\epsilon > 0$, the algorithm always outputs an $\epsilon$-optimal policy after $f(\epsilon, \delta)$ rounds of iterations. It is known that such guarantee is stronger than the usual PAC guarantee and regret guarantee. In this paper, the authors develop uniform-PAC algorithms for linear bandits and RL with linear function approximation. 

The main technical contribution of this paper is a new trick for developing UCB-based algorithms with uniform-PAC guarantee in the linear setting. The authors argue that existing algorithms may not satisfy the uniform-PAC guarantee either because they need to know the number of rounds of iterations in advance, or their confidence bound has a $\log k$ factor which makes it possible for the algorithm to output suboptimal policies infinitely often. To remove the $\log k$ factor in existing UCB-based algorithms, inspired by [6], the authors develop a clever layering method. Specifically, the authors classify all existing actions/data points into groups according to their uncertainty bonus, and each action/data point is added to a group $k$ so that the uncertainty bonus is at most $2^{-k}$. This makes sure that the size of group $k$ is at most $\mathrm{exp}(k)$. For the analysis, instead of doing a union bound over all existing data points which will introduce a $\log k$ factor in the confidence bound, for this new algorithm, we set the failure probably of group $k$ to be roughly $2^{-k}$. Doing so will introduce a factor of $k$ in the confidence bound of group $k$, but that will be ok for the algorithm because the uncertainty bonus is at most $2^{-k}$ for group $k$. The authors further show how to generalize the same technique to linear MDPs. 

Overall, the results and techniques in this paper look interesting and thus I recommend acceptance. For improvement, the authors could consider generalizing their results to generalized linear models / kernels / functions with bounded eluder dimension. For example, it seems possible to use the same technique and the algorithm in [1, 2] to achieve uniform-PAC guarantee for functions with bounded eluder dimension. Moreover, is that possible to give a hard instance so that the algorithm [3] fails to achieve uniform-PAC guarantee provably? Currently the authors only show why the analysis [3] fails to provide uniform-PAC guarantee. This still leaves the possibility that the algorithm could achieve uniform-PAC guarantee through a different analysis. 

Minor Comment: consider changing $(\epsilon,\delta)$-uniform-PAC in Line 160 to uniform-PAC, since uniform-PAC guarantee is not defined for any specific $\epsilon$ and $\delta$. 

[1] Eluder Dimension and the Sample Complexity of Optimistic Exploration

[2] Provably Efficient Reinforcement Learning with General Value Function Approximation

[3] Improved algorithms for linear stochastic bandits
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper a proposes optimistic algorithm for reinforcement learning in linear MDPs and proves the first uniform-PAC bound for this setting. Unlike existing result, this stronger notion of a PAC bound ensures high-probability regret as well as convergence to the optimal policy. Along the way, the paper also provides an algorithm with uniform-PAC guarantees for the contextual linear bandit setting. The algorithms are similar to existing UCB algorithms but employ a sample-splitting technique. This technique essentially ensures the following key property for uniform-PAC results: the confidence bound for a certain state-action pair cannot increase arbitrarily with the number of episodes (as is the case with existing UCBs that typically have log(T) dependence in this setting and therefore increase with T unless an informative observation was gathered).

main_review: This is a solid paper with signifiant and technically interesting contributions. 

Significance: Algorithms that can be run anytime and are guarantees to converge to the optimal policy are highly desirable since in practical scenarios, one is often interested in extracting a single policy eventually but does not know the number of episodes (desired accuracy level epsilon) ahead of time. Existing online-to-batch solutions (e.g. those mentioned for UCB-LSVI) that convert regret to PAC-style guarantees are based on randomly picking one of the policies executed by the algorithm but this is limited to PAC guarantees with 1/delta dependence instead of log(1/delta) and are thus too loose when the failure probability delta is small. 
This work is the first to provide stronger guarantees that imply regret and PAC bounds simultaneously for all epsilon-levels in the function approximation setting, based on the notion of uniform-PAC that has been proposed for the tabular setting. This is an important result and the paper provides technical tools that will be of interest in extending such guarantees beyond the linear setting considered here.

Originality: Using sample splitting in bandits and RL is not new. It has been used for variance reduction in tabular RL as well as earlier algorithms (cf. MoRMax or Delayed-Q learning). However, to the best of my knowledge, the kind of splitting and analysis in this paper is novel, as well as the use to achieve uniform-PAC bounds. I expect this to be a useful tool for other settings as well.

Quality: I have checked the main novel components of the analysis (e.g. Lemma A1 / B1 and A2 / B2 as well as the proof of the main theorems. Besides minor typos, I did not encounter any issues. The analysis is overall well done and presented in a sufficiently detailed and clear way.

Presentation: Overall, the paper does a good job at conveying the main intuition and the details of the analysis. That said, I encourage the authors to do a careful pass on the paper for typos and to improve the writing in certain places (see detailed comments below).

Detailed comments and typos:
- Line 54: round -> rounds
- Line 59: the RL -> RL
- Line 59: on the -> in 
- Section 2.1: the writing is extremely monotonous and should be substantially improved. Every sentence has the exact same structure. It would also be more helpful to relate the existing works better to the contributions made in this paper. 
- Line 141: suboptimality for -> suboptimality gap for
- Remark 3.5: I recommend mentioning that sampling a policy uniformly from the policies executed by the algorithm leads to a poly(1/delta) sample complexity result (and is therefore not considered PAC in the strict original definition) as opposed to a log(1/delta) achieved by the uniform-PAC bound presented in this submission.
- Line 179: Why not just use general sub-Gaussian noise instead of bounding the magnitude? Also, why did the authors adopt a stronger l2 bound on the parameters for the bandit setting (1 vs sqrt(d))? This seems not necessary?
- Sec. 5: provide a reference to Alg 2 in the text.
- Factor H difference compared to UCB-LSVI: The additional factor of sqrt(H) in the regret bound seems to come from the bound in the number of samples per bucket. From what I understand, this is due to the fact that the level l at h can be at most the level at h-1 per episode and therefore additional elements may be added to the levels even though the first condition in line 19 of Alg 2 would hold for higher levels l. This makes the recursive bound on the gap go through nicely but I wonder whether one could avoid that and allow the levels to increase with h per episode (and thus save the additional H dependency). Did the authors explore this direction?
- Line 278: , we -> . We
- Line 300: pair -> pairs
- Line 304 level satisfies -> level that satisfies
- The paper does not discuss the computational cost of the algorithm. By the design of the levels, I think one can show that the number of level can only be logarithmic in k which is not a large additional computational burden. I recommend adding this result and a discussion.
limitations_and_societal_impact: The paper has adequately addressed limitations and potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper designs an algorithm with uniform-PAC for reinforcement learning with linear function approximation. 
main_review: This is the first uniform-PAC algorithm for RL beyond tabular setting. This paper also proves sample complexity on the same order of that of algorithms which are not uniform-PAC.

A major question is in Section 3, the action space $\mathcal{A}$ is required to be finite. Is this requirement fundamental to the design of the algorithms? Can this condition be relaxed?
limitations_and_societal_impact: This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact.
review_title: null

Meta-review: The reviewers find this to be a theoretically strong paper.  I see no reason to disagree and acceptance seems warranted.  However, I feel that the technical notion of a uniform PAC bound is mainly of theoretical interest.  It not clear how much practical insight uniform bounds provide over the insights already provided by standard PAC bounds.  A poster seems appropriate.
Decision: Accept (Poster)