summaries: This paper explores the generality of support vector proliferation and makes the following three contributions: (1) proving a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models. (2) identifying a sharp phase transition in Gaussian feature models. (3) investigating `the phenomenon of support vector proliferation for $\ell_1$ variant of the SVM.

summaries: The paper considers the conditions under which the solution to the classic, hard-margin SVM classifier collapses to the solution of the ordinary linear regression problem.  This is known as support vector proliferation and occurs when all training vectors for the SVM are support vectors.  SVP has been observed previously, and an upper bound placed on the dimension (relative to training set size) required to induce it given.  The paper further elaborates on these results, providing improved lower bounds on the dimension for which it occurs.  The transition region in which SVP occurs is characterised and it's width bounded.  Finally, the authors speculate as to the conditions required for SVP in the $\ell_1$ variant of the SVM, and show experimentally that SVP appears to require much higher dimension for this case.

summaries: This paper investigates the phenomenon of support vector proliferation (SVP), that is, when linear classification with minimum-$\ell_p$-norm hard-margin SVM and minimum-$\ell_p$-norm interpolation yield the same solution. A previous paper showed for $p=2$ that SVP occurs with high probability for certain distributions with (effective) input dimension $d = \Omega(n \log n)$, but not for $d = O(n)$. The authors close this gap by showing that SVP does not occur for $d = o(n \log n)$. The authors further specify a more precise bound for standard Gaussian inputs and provide empirical evidence showing similar behavior for other distributions. Finally, the authors present some other theoretical and empirical results to illuminate the behavior for different $p$.

summaries: This paper proves a super-linear lower bound on the dimension of support vector proliferation (SVP) when features are anisotropic subgaussians. The exact asymptotic threshold of the phase transition in the isotropic Gaussian distribution is also proved. Finally, this paper discussed the case of SVP phase transition for $\ell_1$-SVMs. The experiments on synthetic data sets are also conducted.

summaries: This manuscript investigates the phenomena of \emph{Support Vector proliferation} (SVP) [1,2], in which all points in the training set $x_{i}\in\mathbb{R}^{d}$, $i=1,\cdots, n$ become support vectors, i.e. satisfy $y_{i}\hat{w}^{\top}x_{i}=1$, where $\hat{w}\in\mathbb{R}^{d}$ is the SVM estimator and $y_{i}\in\{-1,1\}$ are the training labels. SVP implies that the SVM estimator coincides with interpolating least-norm linear regression, a fact which has been used in many recent works to study overparametrisation in generalised linear models. In particular, the authors focus in a data model defined by fixed labels $y_{i}$ and sub-Gaussian features $x_{i}$ with zero mean and diagonal covariance $\lambda_{k}$, $k=1, \cdots, d$ (i.e. the labels are independent of the features). The key results are:  - Different equivalent characterisations of SVP for generic $\ell_{p}$, $1< p< \infty$ norm SVM (proposition 1).   - Establishing a lower bound showing that one needs at least $d=n\log{n}$ for SVP to occur in the anisotropic model defined above and $\ell_{2}$-SVM  (Theorem 3). This result tightens the a previous bound from [2] (Theorem 1).  - Establishing a sharp transition at $d = 2n\log{n}$ for SVP in the particular case of isotropic Gaussian data $x_{i}\sim\mathcal{N}(0,I_{d})$, also for $\ell_{2}$-SVM (Theorem 4).  The authors also provide numerical simulations corroborating the theorems, and suggesting that their results apply beyond the theorem's assumptions. Finally, they also provide a conjecture for the equivalent result in the $\ell_1$-SVM case.   [1] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. *Classification vs regression in overparameterized regimes: Does the loss function matter?*, 2020.  [2]: Daniel Hsu, Vidya Muthukumar, and Ji Xu. *On the proliferation of support vectors in high dimensions*.  In Twenty-Fourth International Conference on Artificial Intelligence and Statistics, 391 2021.

abstractText: The support vector machine (SVM) and minimum Euclidean norm least squares regression are two fundamentally different approaches to fitting linear models, but they have recently been connected in models for very high-dimensional data through a phenomenon of support vector proliferation, where every training example used to fit an SVM becomes a support vector. In this paper, we explore the generality of this phenomenon and make the following contributions. First, we prove a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models, matching the upper bounds from previous works. We further identify a sharp phase transition in Gaussian feature models, bound the width of this transition, and give experimental support for its universality. Finally, we hypothesize that this phase transition occurs only in much higher-dimensional settings in the l1 variant of the SVM, and we present a new geometric characterization of the problem that may elucidate this phenomenon for the general lp case.

authors:
Dennis Amelunxen
Peter Bürgisser

title: Intrinsic volumes of symmetric cones

venue: arXiv preprint arXiv:1205.1863,

authors:
Dennis Amelunxen
Martin Lotz
Michael B McCoy
Joel A Tropp

title: Living on the edge: Phase transitions in convex programs with random data

venue: Information and Inference: A Journal of the IMA,

authors:
Peter L Bartlett
Ambuj Tewari

title: Sparseness vs estimating conditional probabilities: Some asymptotic results

venue: Journal of Machine Learning Research,

authors:
Peter L. Bartlett
Philip M. Long
Gábor Lugosi
Alexander Tsigler

title: Benign overfitting in linear regression

venue: Proceedings of the National Academy of Sciences,

authors:
Mikhail Belkin
Daniel Hsu
Ji Xu

title: Two models of double descent for weak features

venue: SIAM Journal on Mathematics of Data Science,

title: The accuracy of the gaussian approximation to the sum of independent variates

venue: Transactions of the American Mathematical Society,

authors:
Arnaud Buhot
Mirta B Gordon

title: Robust learning and generalization with support vector machines

venue: Journal of Physics A: Mathematical and General,

authors:
Emmanuel J Candès
Pragya Sur

title: The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression

venue: The Annals of Statistics,

authors:
Yuan Cao
Quanquan Gu
Mikhail Belkin

title: Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures

venue: arXiv preprint arXiv:2104.13628,

authors:
Niladri S Chatterji
Philip M Long

title: Finite-sample analysis of interpolating linear classifiers in the overparameterized regime

authors:
Shaobing Chen
David Donoho

title: Basis pursuit

venue: In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers,

title: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition

venue: IEEE Transactions on Electronic Computers,

authors:
Rainer Dietrich
Manfred Opper
Haim Sompolinsky

title: Statistical mechanics of support vector networks

venue: Physical Review Letters,

authors:
David Donoho
Jared Tanner

title: Counting faces of randomly projected polytopes when the projection radically lowers dimension

venue: Journal of the American Mathematical Society,

title: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

venue: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences,

title: Some results on convex bodies and banach spaces

venue: Matematika, 8(1):73–102

authors:
Ronald Aylmer Fisher
Leonard Henry Caleb Tippett

title: Limiting forms of the frequency distribution of the largest or smallest member of a sample

venue: In Mathematical proceedings of the Cambridge philosophical society,

authors:
Pascal Germain
Alexandre Lacoste
François Laviolette
Mario Marchand
Sara Shanian

title: A PAC-Bayes sample-compression approach to kernel methods

venue: In ICML,

authors:
Thore Graepel
Ralf Herbrich
John Shawe-Taylor

title: PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification

venue: Machine Learning,

authors:
Trevor Hastie
Andrea Montanari
Saharon Rosset
Ryan J Tibshirani

title: Surprises in highdimensional ridgeless least squares interpolation

venue: arXiv preprint arXiv:1903.08560,

authors:
Trevor J Hastie
Daryl Pregibon

title: Generalized linear models. In Statistical models in S, pages 195–247

authors:
Daniel Hsu
Vidya Muthukumar
Ji Xu

authors:
Ningyuan Huang
David W Hogg
Soledad Villar

title: Dimensionality reduction, regularization, and generalization in overparameterized regressions

venue: arXiv preprint arXiv:2011.11477,

authors:
Ziwei Ji
Matus Telgarsky

title: The implicit bias of gradient descent on nonseparable data

venue: In Conference on Learning Theory,

title: The concentration of measure phenomenon

venue: Number 89. American Mathematical Soc.,

authors:
Tengyuan Liang
Pragya Sur

title: A precise high-dimensional asymptotic theory for boosting and minimum-l1-norm interpolated classifiers

venue: arXiv preprint arXiv:2002.01586,

title: Exact high-dimensional asymptotics for support vector machine

venue: arXiv preprint arXiv:1905.05125,

authors:
Yasaman Mahdaviyeh
Zacharie Naulet

title: Risk of the least squares minimum norm estimator under the spike covariance model

authors:
Dörthe Malzahn
Manfred Opper

title: A statistical physics approach for the analysis of machine learning algorithms on real data

venue: Journal of Statistical Mechanics: Theory and Experiment,

title: Lectures on discrete geometry, volume 212

venue: Springer Science & Business Media,

authors:
Song Mei
Andrea Montanari

title: The generalization error of random features regression: Precise asymptotics and double descent curve

title: Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation

authors:
Vidya Muthukumar
Kailas Vodrahalli
Vignesh Subramanian
Anant Sahai

title: Harmless interpolation of noisy data in regression

venue: IEEE Journal on Selected Areas in Information Theory,

authors:
Vidya Muthukumar
Adhyyan Narang
Vignesh Subramanian
Mikhail Belkin
Daniel Hsu
Anant Sahai

title: Feature selection, l 1 vs. l 2 regularization, and rotational invariance

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Bernhard Schölkopf
Alex J Smola
Robert C Williamson
Peter L Bartlett

title: New support vector algorithms

venue: Neural computation,

authors:
Daniel Soudry
Elad Hoffer
Mor Shpigel Nacson
Suriya Gunasekar
Nathan Srebro

title: The implicit bias of gradient descent on separable data

venue: J. Mach. Learn. Res.,

title: Sparseness of support vector machines

authors:
Ryan Theisen
Jason Klusowski
Michael Mahoney

title: Good classifiers are abundant in the interpolating regime

venue: In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics,

title: Regression shrinkage and selection via the lasso

venue: Journal of the Royal Statistical Society: Series B (Methodological),

title: The cvxopt linear and quadratic cone program solvers, 2010. URL https://www.seas.ucla.edu/~vandenbe/publications/coneprog.pdf

title: Estimation of dependences based on empirical data

title: Estimation in high dimensions: a geometric perspective

venue: In Sampling theory, a renaissance,

authors:
Ke Wang
Christos Thrampoulidis

title: Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization

venue: arXiv preprint arXiv:2011.09148v4,

authors:
Weichen Wang
Jianqing Fan

title: Asymptotics of empirical eigenstructure for high dimensional spiked covariance

venue: Annals of Statistics,

authors:
Ji Xu
Daniel Hsu

title: On the number of variables to use in principal component regression

venue: In Advances in Neural Information Processing Systems

heading: 1 Introduction

text:
The support vector machine (SVM) and ordinary least squares (OLS) are well-weathered approaches to fitting linear models, but they are associated with different learning tasks: classification and regression. In this paper, we study the case in which the models return exactly the same hypothesis for sufficiently high-dimensional data.
The hard-margin SVM is a linear classification model that finds the separating hyperplane that maximizes the minimum margin of error for every training sample. If the training data (x1, y1), . . . , (xn, yn) ∈ Rd × {±1} are linearly separable, then the resulting linear classifier is x 7→ sign (xTwSVM), where wSVM is the solution to the following optimization problem:
wSVM = argmin w∈Rd ∥w∥2 such that yiw Txi ≥ 1, ∀i ∈ [n]. (1)
An example xi is a support vector if the corresponding constraint is satisfied with equality, and the optimal solution wSVM is a linear combination of these support vectors.
Ordinary least squares regression finds the linear function that best fits the training data (x1, y1), . . . , (xn, yn) ∈ Rd × R according to the sum of squared errors. When the solution is not unique, it is natural to take the solution of minimum Euclidean norm; this is the convention we adopt. Taking X := [x1| . . . |xn]T ∈ Rn×d and y := (y1, . . . , yn), the solution is the hypothesis x 7→ wTOLSx where wOLS is the solution to the following: wOLS = argminw∈Rd ∥w∥2 such that XTXw = XTy. In many high-dimensional settings (e.g., where X has full row rank), the solution may in fact interpolate the training data, i.e.,
wOLS = argmin w∈Rd ∥w∥2 such that w Txi = yi, ∀i ∈ [n]. (2)
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Although the optimization problems in (1) and (2) are very different, they have been observed to coincide in very high-dimensional regimes. The study of this support vector proliferation (SVP) phenomenon—in which every training example is a support vector—was recently initiated by Muthukumar et al. [35] and Hsu et al. [23]. Roughly speaking, they show that SVP occurs when d = Ω(n log n) for a broad class of sample distributions, and that SVP does not occur when d = O(n) in an idealized isotropic Gaussian case.
SVP is a phenomenon that connects linear classification and linear regression, topics that have received renewed attention due to the break-down of classical analyses of these methods in high-dimensions. For instance, some analyses of SVM that are based on the number of support vectors become vacuous when this number becomes large [e.g., 19, 20, 44]. Similarly, overparameterized linear regression is typically only studied in noisy settings with explicit regularization. It was not until recently that SVM and OLS have been meaningfully analyzed in these regimes (see Section 1.2), and the connection between the two approaches via SVP has played an important analytical role [9, 35, 46].
In this work, we further examine support vector proliferation with the goal of broadly understanding when and why SVMs and OLS coincide. We pose and study the following questions:
1. How general is the SVP phenomena? What relationship between d and n determines if the solutions to (1) and (2) coincide?
We close the log n gap from the prior work of Hsu et al. [23] by showing that d ≳ n log n is necessary for SVP to occur under a model of independent subgaussian features, even with constant probability. Our lower-bounds hold for a broad class of distributions over xi, and they match the upper-bounds from [23]. This demonstrates that SVP is extremely unlikely to occur in the much-studied d = Θ(n) setting.
2. Is there a sharp threshold separating the occurrence and non-occurrence of this phenomenon? Is this threshold universal across all “reasonable” distributions over each xi?
We hypothesize that a sharp phase transition occurs at d = 2n log n. We rigorously prove this hypothesis for isotropic Gaussian features and quantitatively bound the width of the transition. We experimentally observe the same transition for a wide range of other distributions.
3. Is support vector proliferation specific to the ℓ2 SVM problem? If (1) and (2) are generalized to instead minimize ℓp norms, does this still occur at the same rate?
We re-frame this question with a geometric characterization of the dual of the SVM optimization problem for ℓp norms. We conjecture that a similar phase transition occurs for ℓ1, but also that it requires much larger dimension d; this is supported by preliminary experiments.

heading: 1.1 Outline of our results

text:
Section 2 introduces the SVM and OLS approaches in full generality, our λ-anisotropic subgaussian data model, and prior results about SVP. Several equivalent characterizations of SVP are established (Proposition 1) for use in subsequent sections.
Section 3 characterizes when SVP does not occur for a broad range of distributions (Theorem 3). Our lower-bound on the dimension required for SVP matches the upper-bounds from [23] in the isotropic Gaussian setting, resolving the open question from that work, and also gives new lower-bounds for anisotropic cases. The proof works by tightly controlling the spectrum of the Gram matrix and establishing anti-concentration via the Berry-Esseen Theorem.
Section 4 establishes a sharp threshold of d = 2nlog n for SVP in the case of isotropic Gaussian samples, and also characterize the width of the phase transition (Theorem 4).
Section 5 provides empirical evidence that the sharp threshold observed in Section 4 holds for a wide range of random variables. Rigorous statistical methodology inspired by Donoho and Tanner [16] is used to test our “universality hypothesis” that the probability of SVP does not depend on the underlying sample distribution as d and n become large.
Section 6 asks the questions about SVP from the preceding sections in the context of ℓ1-SVM and minimum ℓ1-norm interpolation. Specifically, the SVP threshold for ℓ1 is conjectured to occur for d = ω(n log n). Evidence for this conjecture is provided in a simulation study and in geometric arguments about random linear programs.

heading: 1.2 Related work

text:
Prior works connecting SVP and generalization. Muthukumar et al. [35] initiate the study of SVP in part to facilitate generalization analysis of the SVM in very high-dimensional settings. Their work, as well as the contemporaneous work of Chatterji and Long [10], shows that the SVM enjoys low test error in certain regimes where classical learning-theoretic analyses would otherwise yield vacuous error bounds. (In fact, one of the settings in [10] requires polynomially-higher dimension than is typically studied: d = Ω(n2 log n).) The coincidence between SVM and OLS identified by Muthukumar et al. was also more recently used by Wang and Thrampoulidis [46] and Cao et al. [9] for analyses of linear classification in very high dimensions under different data distributions.
The generalization analysis of Muthukumar et al. concerns a data model inspired by the spiked covariance model of Wang and Fan [47]. They identify a regime of overparameterization where the hard-margin SVM classifier has good generalization (i.e., classification risk going to 0) even when all the training samples are supoort vectors. Our new lower bound can be regarded as establishing a limit on this approach to the analysis of SVM; specifically, if the (effective) dimension is not sufficiently large, the OLS and SVM solutions may not coincide.
Prior analyses of number of support vectors. Besides its relevance to generalization analysis, the number of support vectors in an SVM model is an interesting quantity to study in its own right. Hsu et al. [23] sharpen and extend the analysis of Muthukumar et al. [35] about SVP in the independent features model that we also adopt. They prove that SVM on n samples with d independent subgaussian components coincides with OLS when d = Ω(n log n) with probability tending to 1. They also give a converse result stating that the coincidence fails with constant probability when d = O(n) in the isotropic Gaussian feature model. (We give these results here as Theorems 1 and 2 respectively.) Our results generalize and tighten the latter bound to tell an asymptotically sharp story about the phase transition for both isotropic and anisotropic random vectors with subgaussian components. Our specific analysis for the isotropic Gaussian case gives the exact point of the phase transition.
The number of support vectors is also studied in the context of variants of SVM [3, 39], including the soft-margin SVM [12] and the ν-SVM [37]. In these cases, the asymptotic number of support vectors is shown to be related to the noise rate in the problem. The setups we study are linearly separable, which makes it possible to study the hard-margin SVM (without regularization). The hard-margin SVM is also of interest because it captures the implicit bias of gradient descent on the logistic loss objective for linear predictors [25, 38].
Phase transitions have been studied in the context of linear classification [8, 13, 27, 40], and SVMs in particular [7, 14, 28, 30], but most study qualitative changes in behavior other than support vector proliferation. The most relevant is the study of Buhot and Gordon [7], who employ techniques from statistical physics to show the existence of phase transitions for the generalization error, margin size, and number of support vectors as n and d = Θ(n) become arbitrarily large. While they characterize the fraction of samples that are support vectors, they do not address our question about when all samples are support vectors, not just a large fraction. Indeed, our results demonstrate that their regime where d grows linearly with n will not exhibit support vector proliferation when n and d in the limit.
Overparameterized linear regression. There has been a recent flurry of analyses of overparameterized linear regression models [e.g., 4, 5, 21, 24, 29, 32–35, 47, 48]. Many of these analyses are carried out in the d = Θ(n) asymptotic regime, whereas our work studies a phase transition that occurs in a much higher-dimensional regime. The notions of effective dimensions we use are present in the analyses of Bartlett et al. [4] and Muthukumar et al. [35], and the latter work identifies regimes where SVM and OLS coincide and enjoy good performance for both classification and regression.
High-dimensional geometry and universality. Our conjecture about support vector proliferation for ℓ1-SVMs derives inspiration from studies of high-dimensional geometric phase transitions, particularly those by [1, 2, 15]. These results consider the geometry of random polytopes. Amelunxen and Bürgisser [1] establish phase transitions on the feasibility and boundedness of the solutions to random linear programs, Amelunxen et al. [2] extend these results to characterize when ℓ1-norm minimizing solutions to sparse recovery problems are exactly correct, and Donoho and Tanner [15] bound the number of faces of random polytopes. We also borrow heavily from [16] when designing our experiments in Section 5 to test the universality hypothesis.

heading: 2 Preliminaries

text: This section introduces notation, as well as the optimization problems and data models we consider. We also define support vector proliferation and prove the equivalence of different formulations.

heading: 2.1 Notation

text:
For λ ∈ Rd+, we define the ℓ2 and ℓ∞ dimension proxies as d2 := ∥λ∥21/∥λ∥22 and d∞ := ∥λ∥1/∥λ∥∞ Let [n] := {1, . . . , n}. For some vector w ∈ Rn and matrix A ∈ Rn×d, we let wi and Ai denote the ith element of w and row of A respectively; likewise, we let A·,j ∈ Rn represent the jth column of A. We abuse notation to let w\i = (w1, . . . , wi−1, wi+1, . . . , wn) ∈ Rn−1, w[m] = (w1, . . . , wm) ∈ Rm, w\[m] = (wm+1, . . . , wn) ∈ Rn−m, and w[m]\i = (w[m])\i ∈ Rm−1 for i ∈ [m] and m ∈ [n]. Analogous notation holds for A\i, A[m], A\[m], and A[m]\i. We frequently consider the Gram matrix K := XXT ∈ Rn×n for feature matrix X ∈ Rn×d; for these matrices, we let K\i = X\iXT\i ∈ R
(n−1)×(n−1) and analogously define K[m], K\[m], and K[m]\i. Let µmax(A) and µmin(A) represent the largest and smallest eigenvalues of the matrix A respectively, and let ∥A∥ be the operator norm of A. For some vector y ∈ Rn, we let diag(y) ∈ Rn×n be a diagonal matrix with (diag(y))i,i = yi. Throughout, boldface characters refer to random variables.

heading: 2.2 Optimization problems

text:
We consider the hard-margin support vector machine (SVM) optimization problem and ask under what conditions one may expect all the slackness conditions to be satisfied. We consider training samples (x1, y1), . . . , (xn, yn) ∈ Rd×{±1} in a high-dimensional regime where d ≫ n with design matrix X := [x1| . . . |xn]T ∈ Rn×d and Gram matrix K = XXT ∈ Rn×n. In full generality, the separating hyperplane corresponding to the ℓp-SVM problem for some p ≥ 1 is the solution to the following optimization problem:
min w∈Rd ∥w∥p such that yiw Txi ≥ 1, ∀i ∈ [n]. (SVM Primal)
Our results in Sections 3–5 concern p = 2, and we discuss p = 1 in Section 6. It is worth mentioning that feasibility is not a concern in the settings we consider.1 An example (xi, yi) is called a support vector if it lies exactly on the margin defined by separator w, or equivalently if yiwTxi = 1. It is well-known that w can be represented as a non-negative linear combination of all yixi where xi is a support vector [43].
We contrast the weights of the classifier returned by SVM Primal with the weights of minimum ℓp-norm that satisfy the normal equations of ordinary least squares (OLS). In the case where the training data can be linearly interpolated, this optimization problem is:
min w∈Rd ∥w∥p such that yiw Txi = 1, ∀i ∈ [n]. (Interpolation Primal)
Per the convention mentioned in the introduction, the solution of (Interpolation Primal) when p = 2 is referred to as ordinary least squares. Feasibility is ensured as long as the feature vectors xi are linearly independent.

heading: 2.3 Equivalent formulations of SVP

text:
We study the phenomenon of support vector proliferation (SVP), i.e., the occurrence in which every example xi is a support vector. Because xi is a support vector if yiwTxi = 1, this occurs if and only if the solution of (SVM Primal) coincides exactly with that of (Interpolation Primal). Here, we analyze those formulations to show equivalent conditions needed for SVP, which we give in Proposition 1. Before presenting the proposition, we introduce the notation needed to use the alternate formulations.
1When d ≥ n, we are always able to find a separating hyperplane since the features are linearly independent with high probability. In fact, a theorem of Cover [13] shows that feasibility holds with high probability under mild distributional assumptions even for d > n/2.
We translate the relationship between the two primal optimization problems into the dual space. Taking A = diag(y)X ∈ Rn×d, the dual of the optimization problem (Interpolation Primal) is:
max α∈Rn n∑ i=1 αi such that ∥ATα∥q ≤ 1. (Interpolation Dual)
The dual of (SVM Primal) is (Interpolation Dual) with an additional constraint that α ∈ Rn+. Let T = { ∑n i=1 aiAi : ∑n
i=1 ai = 1} denote the affine plane passing through the rows of A, and let T+ = { ∑n i=1 aiAi : ∑n i=1 ai = 1, ai ≥ 0} be the convex hull of the rows of A. In addition, for
i ∈ [n], let T\i = { ∑ i′ ̸=i ai′Ai′ : ∑
i′ ̸=i ai′ = 1}. We denote ΠT(0) as the ℓq-norm projection of the origin onto T, which is uniquely defined for 1 < q < ∞. Proposition 1. Let 1 < p < ∞ and q = (1− 1/p)−1, and consider any (X, y) ∈ Rn×d × {±1}n. Suppose K is invertible. Then, the following are equivalent:
(1) SVP occurs for ℓp-SVM. (2) The solutions w to (SVM Primal) and (Interpolation Primal) are identical. (3) The optimal solution to (Interpolation Dual) lies within the interior of Rd+. (4) ΠT(0) ∈ T+.
Moreover, if p = 2, then properties (1)–(4) are also equivalent to the following:
(5) For all i ∈ [n], yiyT\iK −1 \i X\ixi = yiΠT\i(0) Txi/∥ΠT\i(0)∥22 < 1.
This dual framework in (3) and (4) gives an alternative geometric structure to consider for this problem. For the ℓ2-case, this formulation draws from the fact that the separating hyperplane obtained from an SVM is represented as a linear combination of support vectors. Although the ℓ1 case is not technically covered by Proposition 1 (due to the non-strict convexity of ℓ1 norm), our analysis still gives useful insights, and we explore this case specifically in Section 6.
We prove Proposition 1 in Appendix A. The equivalence between (1) and (5) in the p = 2 case was proved by Hsu et al. [23, Lemma 1]. Our alternative proof is based on establishing the equivalence of (4) and (5) and draws heavily from our geometric formulation of SVP.

heading: 2.4 Data model

text:
We use the data model of Hsu et al. [23], where every labeled sample (xi, yi) has xi drawn from an anisotropic subgaussian distribution with independent components and arbitrary fixed labels yi. Definition. For some λ ∈ Rd≥0, we say (X, y) ∈ Rn×d × {±1}n (as well as (X,Z, y) ∈ Rn×d × Rn×d × {±1}n) is a λ-anisotropic subgaussian sample if: y = (y1, . . . , yn) ∈ {±1}n are fixed (non-random) labels; Z := [z1| . . . |zn]T ∈ Rn×d is a matrix of independent 1-subgaussian random variables with E[zi,j ] = 0 and E[z2i,j ] = 1; and X := [x1| . . . |xn]T = Z diag(λ)1/2 ∈ Rn×d. We say (X, y) is an isotropic subgaussian sample if it is λ-anisotropic for λ = (1, . . . , 1). Finally, we say (X, y) is an isotropic Gaussian sample if it is isotropic subgaussian and each xi ∼ N (0, Id).
We only consider fixed labels y that do not depend on X. However, we do not consider this to be a major limitation of this work. As discussed before, Cover [13] shows that linear separability is overwhelmingly likely in the high-dimensional regimes we consider. Moreover, our results can be extended to a setting where yi = sign (vTxi) for some fixed weight vector v.

heading: 2.5 Previous results

text:
We tighten and generalize the characterization of the SVP threshold by Hsu et al. [23]. We give versions of their results that are directly comparable to our results in Sections 3 and 4. Theorem 1 (Theorem 1 of [23]). Consider a λ-anisotropic subgaussian sample (X, y) and any δ ∈ (0, 1). If d∞ = Ω(n log(n) log( 1δ )), then SVP occurs for ℓ2-SVM with probability at least 1− δ. Theorem 2 (Theorem 3 of [23]). Consider an isotropic Gaussian sample (X, y). For some constant δ ∈ (0, 1), if d = O(n), then SVP occurs for ℓ2-SVM with probability at most δ.
They note the logarithmic separation between Theorems 1 and 2 and the limitations of the data model used in Theorem 2. The authors pose an improvement in generality and asymptotic tightness to their lower-bound as an open problem, which we resolve in the subsequent sections.

heading: 3 SVP threshold for anisotropic subgaussian samples

text:
We closely characterize when support vector proliferation does and does not occur through the following theorem, which serves as a converse to Theorem 1. Theorem 3 (Lower-bound on SVP threshold for anisotropic subgaussians). Consider a λ-anisotropic subgaussian sample (X, y) and any δ ∈ (0, 12 ). For absolute constants C1, C2, C3, C4, assume that λ and n satisfy
n ≥ C1 ( log 1
δ
)2 , d2 ≤ C2n log n, d∞ ≥ C3n log 1
δ , and d2∞ ≥ C4d2n. (3)
Then, SVP occurs for ℓ2-SVM with probability at most δ. Remark 1. If each xi is drawn from a Gaussian distribution, then we could instead permit xi to have any positive semi-definite covariance matrix Σ ∈ Rd×d with eigenvalues λ1, . . . , λd due to rotational invariance. Remark 2. In addition, the result can be generalized to subgaussian xi with general variance proxies γ ≥ 1. We present the current version for the sake of simplicity and note that the generalization is straightforward.
In the case where (X, y) is an isotropic subgaussian sample, Theorem 3 and Theorem 1 (from [23]) together establish that the threshold for SVP occurs at d = Θ(n log n). Theorem 3 sharpens and generalizes the partial converse of [23] given in Theorem 2.
Theorem 3 does not depend explicitly on the ambient dimension d; instead, it only involves the effective dimension proxies d2 and d∞, which can be finite even if d is infinite. Thus, the result readily extends to infinite-dimensional Hilbert spaces.
We prove the theorem in Appendix B and briefly summarize the techniques here. By Proposition 1, it suffices to show that with probability 1− δ, K is invertible and
max i∈[n]
yiy T \iK −1 \i X\ixi ≥ 1, (4)
where K\i := X\iXT\i. This same equivalence underlies the proof of Theorem 2 in [23]. However, their application of this equivalence is limited because they avoid issues of dependence between random variables by instead lower-bounding the probability that y1yT\1K −1 \1 X\1x1 ≥ 1. This forces their bound to hold only when d = O(n). We obtain a tighter bound by separating the first m samples (denoted X[m]) for some carefully chosen m and relating the term to the maximum of m independent random variables. To do so, we lower-bound the left-hand side of (4) with the following decomposition:
max i∈[m]
[ yiy T
\i ( K−1\i − 1
∥λ∥1 In−1
) X\ixi + 1
∥λ∥1 yiy
T [m]\iX[m]\ixi + 1
∥λ∥1 yiy
T \[m]X\[m]xi
] .
We prove that this decomposition (and hence, also (4)) is at least 1 with probability 1− δ by lowerbounding the three terms with Lemmas 1, 3, and 4 (given in Appendix B). We bound the first two terms for all i ∈ [m] by employing standard concentration bounds for subgaussian and subexponential random variables and by tightly controlling the spectrum of K\i. To bound the third term, we relate the quantity for each i ∈ [m] to an independent univariate Gaussian with the Berry-Esseen theorem and apply standard lower-bounds on the maximum of m independent Gaussians.
The assumptions in (3) are all intuitive and necessary for our arguments. The first assumption ensures that enough samples are drawn for high-probability concentration bounds to exist over collections of n variables. The second assumption guarantees the sub-sample size m is sufficiently large to have predictable statistical properties; this is asymptotically tight with its counterpart in Theorem 1 up to a factor of log 1δ . The third ensures that the variance of each yiy T \iK −1 \i X\ixi term is sufficiently small. The fourth assumption rules out λ-anisotropic subgaussian distributions with ∥λ∥22 ≪ ∥λ∥2∞n, where a single component of each xi is disproportionately large relative to others and causes unfavorable anti-concentration properties.

heading: 4 Exact asymptotic threshold for Gaussian samples

text:
Section 3 shows the existence of a change in model behavior when d = Θ(n log n) without identifying a precise threshold where this phase transition appears. Here, we refine that analysis for the isotropic Gaussian case to find such an exact threshold. That is, if d = 2τn log n, as n becomes large, SVP will occur when τ > 1 and will not occur when τ < 1. Roughly speaking, this phenomenon stems from the fact that terms in (4) are weakly correlated, which causes (4) to behave similarly to a maximum of independent Gaussians. Furthermore, we characterize the rate at which the phase transition sharpens. The following theorem shows that if the convergence τ → 1 is slow enough, then the asymptotic probabilities of SVP are degenerate and the width of the transition is bounded.
Theorem 4 (Sharp SVP phase transition). Let (X, y) be an isotropic Gaussian sample. Let (ϵn)n≥1 be any sequence of positive real numbers such that lim supn→∞ ϵn < 2− c1 for some c1 > 0 and lim infn→∞ ϵn √ log n > C2 for some C2 > 0 depending only on c1. Then,
lim n→∞ P[SVP occurs for ℓ2-SVM] = { 0 if d = (2− ϵn)nlog n, 1 if d = (2 + ϵn)nlog n.
Remark 3. Theorem 4 characterizes the width of the phase transition: the difference wn between the values of d where the probability of SVP is (say) 0.9 and 0.1 satisfies wn = O(n √ log n).
It remains an open problem to determine if this transition width estimate is sharp. Specifically, the bound can be sharpened by exhibiting some sequence ϵn for which the asymptotic probability of support-vector proliferation is non-degenerate.
The proof of Theorem 4 is given in Appendix C. In the case where d = (2− ϵn)nlog n, the proof mirrors that of Theorem 3, but deviates in the final step by using the limiting distribution of the maximum of independent Gaussians. When d = (2 + ϵn)nlog n, we follow the basic argument in the proof of Theorem 1 from [23], but we sharpen the analysis by taking advantage of Gaussianity to find the limiting probability as n → ∞.

heading: 5 Experimental validation of SVP phase transition and universality

text:
While Theorem 4 identifies the exact SVP phase transition for only isotropic Gaussian samples, we demonstrate experimentally that a similarly sharp cutoff occurs for a broader category of data distributions. These experiments suggest that the phase transition phenomenon extends beyond the distributions with independent subgaussian components considered in Theorem 3, and that it occurs at the same location (d = 2n log n), with the transition sharpening as n → ∞. Our simulation procedure is as follows. We generate data sets (X, y) ∈ Rn×d × {±1}n, where y ∈ {±1}n is a fixed vector of labels with exactly n/2 positive labels, and x1, . . . ,xn ∼i.i.d. D⊗d where D is one of six sample distributions on R. For each data set, we check for SVP by solving the problem in (Interpolation Primal), and checking if its solution additionally satisfies the constraints from (SVM Primal). Let p̂ := p̂(n, d;D,M) denote the observed frequency of SVP in M = 400 independent trials when X ∈ Rn×d is generated using D. (Full details are given in Appendix D.1.) Figure 1 shows a heat map of p̂(n, d;D,M) with M = 400. The striking similarity across the distributions suggests that SVP is a universal phenomenon for a broad class of sample distributions that vary qualitatively in different aspects: biased vs. unbiased, continuous vs. discrete, bounded vs. unbounded, and subgaussian vs. non-subgaussian. Moreover, the boundary at which the sharp transition occurs is visibly indistinguishable across the different sample distributions.
We also investigate the universality of SVP using statistical methodology inspired by Donoho and Tanner [16]. Specifically, we model p̂ using Probit regression to test our universality hypothesis: that the occurrence of SVP for ℓ2-SVM on data with independent features matches the behavior under Gaussian features as n and d grow large. Our model is M · p̂ ∼ Binom(p(n, d;D),M), where
p(n, d;D) = Φ ( µ(0)(n,D) + µ(1)(n,D)× τ + µ(2)(n,D)× log τ ) with µ(i)(n,D) = µ(i)0 (D) + µ (i) 1 (D)√
n .
Here, Φ(t) is the standard normal distribution function, τ = d/(2n log n), and the model parameters are µ(i)0 (D) and µ (i) 1 (D) for i ∈ {0, 1, 2} and the six different distributions D (shown in Table 1 in Appendix D.1). Figure 2 visualizes the fitted Probit function p for fixed n and τ and demonstrates that the model provides a very accurate approximation of p̂.
The universality hypothesis corresponds to the model in which the parameters µ(i)0 (D) are “tied together” (i.e., forced to be the same) for all distributions D. That is, only the parameters scaled down by a factor of √ n, µ(i)1 (D), are allowed to vary with D. The scaling ensures that their effect tends to zero as n → ∞. The alternative (non-universality) hypothesis corresponds to the model in which all parameters (both µ(i)0 (n,D) and µ (i) 1 (n,D) for each i) are allowed to vary with D. We compare the models’ goodness-of-fit using analysis of deviance [22]. Our main finding is that the experimental data are consistent with the universality hypothesis (and also that we can reject a null hypothesis in which all parameters are “tied together” for all D). The details and model diagnostics are given in Appendix D.2.
Finally, in Appendix D.3, we provide empirical support for the generality of Remark 3, namely that the transition width is roughly n √ log n for data models other than Gaussian ensembles.

heading: 6 SVP phase transition for ℓ1-SVMs?

text:
Because both the SVM and linear regression problems can be formulated for general ℓp-norms, we can ask similar questions about when their solutions coincide. Here, we examine the ℓ1 case: the coincidence of SVM with an ℓ1-penalty and ℓ1-norm minimizing interpolation (also called Basis Pursuit [11]). Linear models with ℓ1 regularization are often motivated by the desire for sparse weight vectors [e.g., 11, 34, 36, 41].
Based on experimental evidence and the differences in high-dimensional geometry between ℓ∞ and ℓ2 balls, we conjecture that SVP for ℓ1-SVMs only occurs in a much higher-dimensional regime.
Conjecture 1. Let (X, y) ∈ Rn×d × Rn be an isotropic Gaussian sample. Then, the probability of SVP occurring for an ℓ1-SVM with X and y undergoes a phase transition around d = f(n), for some
f(n) = ω(n log n). Formally, there exist positive constants c and c′ with c ≤ c′ such that
lim n→∞ P [SVP occurs for ℓ1-SVM] = { 0 if d < cf(n), 1 if d > c′f(n).
Conjecture 1 is consistent with our preliminary experimental findings, summarized in Figure 3. It shows larger values of d relative to n are needed to ensure SVP for ℓ1-SVMs and that the transition appears to be less sharp. Indeed, the experiments indicate that the true phase transition may occur when d is asymptotically much larger than n log n. They do not rule out the possibility that the transition may even require d = exp(Ω(n)). Further experimental details are given in Appendix E.1.
Answering whether support vector proliferation occurs in the ℓ1 case is equivalent to determining whether the optimal solution α∗ to (Interpolation Dual) problem lies in the positive orthant Rn+.2 In the ℓ1 case, we have q = ∞, so solving the problem amounts to characterizing the solutions to the
2While Proposition 1 does not imply this equivalence for ℓ1-SVMs for arbitrary data, the results of the proposition are valid for isotropic Gaussian samples, because the corresponding ℓ∞ projection ΠT(0) in those cases is well-defined almost surely.
following linear program for data matrix A = diag(y)X ∈ Rn×d:
max α∈Rn n∑ i=1 αi s.t. − 1 ≤ ATα ≤ 1. (Dual L1)
There is a line of work that gives high probability guarantees about whether related random linear programs are feasible and where their solutions reside [1, 2]. Similar analyses of random linear programs may be useful for understanding how large d must be to have α∗ ∈ Rn+, and we carry out a preliminary characterization in Appendix E.
Conjecture 1 and the other questions raised in this work point to a broader scope of investigations about high-dimensional phenomena and universality concerning optimization problems commonly used in machine learning and statistics. Our results, along with those from prior works, provide new analytic and empirical approaches that may prove useful in tackling these questions.
Acknowledgments and Disclosure of Funding
D. Hsu acknowledges support from NSF grants CCF-1740833 and IIS-1563785, NASA ATP grant 80NSSC18K109, and a Sloan Research Fellowship. C. Sanford acknowledges support from NSF grant CCF-1563155 and a Google Faculty Research Award to D. Hsu. N. Ardeshir acknowledges support from Columbia Statistics Department. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. We acknowledge computing resources from Columbia University’s Shared Research Computing Facility project, which is supported by NIH Research Facility Improvement Grant 1G20RR030893-01, and associated funds from the New York State Empire State Development, Division of Science Technology and Innovation (NYSTAR) Contract C090171, both awarded April 15, 2010.

title: Support vector machines and linear regression coincide with very high-dimensional features


summaries: This paper deals with online learning of policies for MDPs. Its main novelty is considering the "navigation constraints" related to this online setting where, in contrast with an episodic setting, the system must learn the policy in a single episode without being able to reset to an initial state. Bounds on sample complexity are derived and an algorithm for learning the best policy by exploiting the lower bounds is proposed.

summaries: The paper studies the best policy identification (BPI) problem in Markov Decision Processes, under navigation constraints, i.e., when accessing a single trajectory from the environment, as opposed to the generative model setting. The paper focuses first on a lower bound on the sample complexity obtained by extending existing results. Then, an algorithm is introduced, and the corresponding sample complexity is analyzed. The contribution is mainly theoretical.

summaries: The paper studies best-policy identification in discounted MDPs with online interaction. The authors first derive an information-theoretic lower bound on the sample complexity of any \delta-correct algorithm for this problem. The lower bound is given as the solution to a non-convex optimization problem for which a convex relaxation is provided. The authors then design an algorithm using the standard template for building pure exploration strategies from asymptotic lower bounds (GLR test + tracking + forced exploration). For this algorithm, the authors derive an asymptotic (as \delta -> 0) upper bound on the sample complexity that matches the value of the relaxed optimization problem up to a factor 2.

summaries: The paper studies problem-dependent sample complexity bounds for best policy identification (BPI) in finite MDPs under the infinite horizon discounted criterion. The agent interacts sequentially (online) with the MDP, a weaker assumption than the generative model required by previous work in the same setting. Its main contributions are:  (i)  A problem-dependent lower bound on the sample complexity that takes into account navigation constraints;  (ii) Since the lower bound is defined as the solution to a non-convex optimization problem, the paper uses a convex relaxation introduced by [MP20] to derive a relaxed lower bound;  (iii) An algorithm whose upper bound matches the relaxed lower bound up to a factor 2.

summaries: This work talks about best policy identification problem in discounted infinite MDP. Instead of assuming a generator, this work is on the online setting of MDP, where the agent can only collect state action pairs through online interaction with the environment. In theory, the work provides a lower bound of the BPI problem. Then the work provides a model-based algorithm MDP-NaS, which is shown to converge to the optimal policy.

abstractText: We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose a problem-dependent lower bound on the average number of steps required before a correct answer can be given with probability at least 1− δ. We further provide the first algorithm with an instance-specific sample complexity in this setting. This algorithm addresses the general case of communicating MDPs; we also propose a variant with a reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the generative setting [MP21], where the agent could at each step query the random outcome of any (state, action) pair. In contrast, we show here how to deal with the navigation constraints, induced by the online setting. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.

authors:
Alekh Agarwal
Mikael Henaff
Sham Kakade
Wen Sun

title: Pc-pg: Policy cover directed exploration for provable policy gradient learning

venue: Advances in Neural Information Processing Systems,

authors:
Peter Auer
Thomas Jaksch
Ronald Ortner

title: Near-optimal regret bounds for reinforcement learning

authors:
Alekh Agarwal
Sham Kakade
Lin F. Yang

title: Model-based reinforcement learning with a generative model is minimax optimal. volume

venue: Proceedings of Machine Learning Research,

authors:
Mohammad Gheshlaghi Azar
Rémi Munos
Hilbert J Kappen

title: Minimax pac bounds on the sample complexity of reinforcement learning with a generative model

venue: Machine learning,

authors:
Apostolos N. Burnetas
Michael N. Katehakis

title: Optimal adaptive policies for markov decision processes

venue: Mathematics of Operations Research,

authors:
Thomas M. Cover
Joy A. Thomas

title: Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)

authors:
Rémy Degenne
Wouter M. Koolen
Pierre Ménard

title: Non-asymptotic pure exploration by solving games

venue: In NeurIPS,

authors:
O.D. Domingues
Pierre M’enard
E. Kaufmann
Michal Valko

title: Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited

venue: In ALT,

authors:
Thomas Dietterich
Majid Taleghan
Mark Crowley

title: Pac optimal planning for invasive species management : Improved exploration for reinforcement learning from simulator-defined mdps

authors:
Eyal Even-Dar
Shie Mannor
Yishay Mansour

title: Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems

venue: Journal of Machine Learning Research, 7:1079–1105,

authors:
Sarah Filippi
Olivier Cappé
Aurélien Garivier

title: Optimism in reinforcement learning and kullback-leibler divergence

venue: In Allerton Conference on Communication, Control, and Computing,

title: Efficient reinforcement learning

venue: In COLT ’94,

authors:
G. Fort
É. Moulines
P. Priouret

title: Convergence of adaptive and interacting markov chain monte carlo algorithms

authors:
Fei Feng
W. Yin
Alekh Agarwal
Lin F. Yang

title: Provably correct optimization and exploration with non-linear policies

authors:
Aurélien Garivier
Emilie Kaufmann

title: Optimal best arm identification with fixed confidence

venue: 29th Annual Conference on Learning Theory,

authors:
A. Garivier
Emilie Kaufmann

title: Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models

venue: arXiv preprint, Statistics Theory,

title: Heyde. 2 - inequalities and laws of large numbers

venue: Martingale Limit Theory and its Application, Probability and Mathematical Statistics: A Series of Monographs and Textbooks,

authors:
Anders Jonsson
Emilie Kaufmann
Pierre Menard
Omar Darwiche Domingues
Edouard Leurent
Michal Valko

title: Planning in markov decision processes with gap-dependent sample complexity

title: On the sample complexity of reinforcement learning

venue: PhD thesis,

authors:
Emilie Kaufmann
Olivier Cappé
Aurélien Garivier

title: On the complexity of bestarm identification in multi-armed bandit models

venue: The Journal of Machine Learning Research,

authors:
Emilie Kaufmann
Wouter M. Koolen

title: Mixture martingales revisited with applications to sequential tests and confidence intervals

venue: arXiv preprint,

authors:
Emilie Kaufmann
Pierre Ménard
Omar Darwiche Domingues
Anders Jonsson
Edouard Leurent
Michal Valko

title: Adaptive reward-free exploration

venue: Proceedings of the 32nd International Conference on Algorithmic Learning Theory,

authors:
Michael Kearns
Yishay Mansour
Andrew Y. Ng

title: A sparse sampling algorithm for near-optimal planning in large markov decision processes

venue: In Proceedings of the 16th International Joint Conference on Artificial Intelligence - Volume 2,

authors:
Michael Kearns
Satinder Singh

title: Finite-sample convergence rates for q-learning and indirect algorithms

venue: In Proceedings of the 11th International Conference on Neural Information Processing Systems,

authors:
Gen Li
Changxiao Cai
Yuxin Chen
Yuantao Gu
Yuting Wei
Yuejie Chi

title: Is q-learning minimax optimal? a tight sample complexity analysis, 2021

authors:
David A. Levin
Yuval Peres
Elizabeth L. Wilmer

title: Markov chains and mixing times

venue: American Mathematical Society,

authors:
T.L. Lai
H. Robbins

title: Asymptotically efficient adaptive allocation rules

venue: Advances in Applied Mathematics,

authors:
Gen Li
Yuting Wei
Yuejie Chi
Yuantao Gu
Yuxin Chen

title: Breaking the sample size barrier in model-based reinforcement learning with a generative model

title: Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction, 2020

authors:
Pierre M’enard
O.D. Domingues
Anders Jonsson
E. Kaufmann
Edouard Leurent
Michal Valko

title: Fast active learning for pure exploration in reinforcement learning

authors:
Aymen Al Marjani
Alexandre Proutiere

title: Adaptive sampling for best policy identification in markov decision processes

venue: Proceedings of the 38th International Conference on Machine Learning,

title: Simple bayesian algorithms for best arm identification

venue: In Proceedings of the 29th Conference On Learning Theory,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction

title: Perturbation theory and finite markov chains

venue: Journal of Applied Probability,

authors:
Alexander L Strehl
Michael L Littman

title: An analysis of model-based interval estimation for markov decision processes

venue: Journal of Computer and System Sciences,

authors:
Aaron Sidford
Mengdi Wang
Xian Wu
Lin Yang
Yinyu Ye

title: Near-optimal time and sample complexities for solving markov decision processes with a generative model

venue: Advances in Neural Information Processing Systems

title: Algorithms for Reinforcement Learning

venue: Morgan and Claypool Publishers,

title: Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

venue: arXiv e-prints, page arXiv:1704.01869,

authors:
Andrew Wagenmaker
Max Simchowitz
Kevin Jamieson

title: Beyond No Regret: Instance-Dependent PAC Reinforcement Learning

venue: arXiv e-prints, page arXiv:2108.02717,

authors:
Andrea Zanette
Ching-An Cheng
Alekh Agarwal

title: Cautiously optimistic policy optimization and exploration with linear function approximation

authors:
Andrea Zanette
Mykel J Kochenderfer
Emma Brunskill

title: Almost horizon-free structure-aware best policy identification with a generative model

heading: 1 Introduction

text:
Somewhat surprisingly, learning in a Markov Decision Process is most often considered under the performance criteria of consistency or regret minimization (see e.g. [SB18, Sze10, LS20] and references therein). Regret minimization (see e.g. [AJO09, FCG10]) is particularly relevant when the rewards accumulated during the learning phase are important. This is however not always the case: for example, when learning a game (whether Go, chess, Atari, or whatever), winning or losing during the learning phase does not really matter. One may intuitively think that sometimes getting into difficulty on purpose so as to observe unheard situations can significantly accelerate the learning process. Another example is the training of robot prototypes in the factory: a reasonably good policy is first searched, regardless of the losses incurred, that can serve as an initialization for a second phase regret-minimization mode that starts when the robot is deployed. It is hence also of great practical importance to study the sample complexity of learning, and to work on strategies that might improve, in this perspective, on regret minimizing algorithms.
In this work, we are interested in the best policy identification (BPI) problem for infinite-horizon discounted MDPs. This framework was introduced by [Fie94] under the name of PAC-RL. In BPI the algorithm explores the MDP until it has gathered enough samples to return an ε-optimal policy with probability at least 1− δ. Crucially, the algorithm halts at a random time step, determined by a
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
stopping rule which guarantees that the probability of returning a wrong answer is less that δ. The optimality of BPI algorithms is measured through their sample complexity, defined as their expected stopping time. Best policy identification in MDPs has been mostly investigated under the lens of minimax-optimality. The minimax framework may be overly pessimistic by accounting for the worst possible MDP, whereas an algorithm with instance-specific guarantees can adapt its exploration procedure to the hardness of the MDP instance that it faces. Recently, a few works made the first attempts towards understanding the instance-specific sample complexity of reinforcement learning. However, they typically either make simplifying assumptions such as access to a generative model [ZKB19, MP21], or restrict their attention to episodic MDPs [WSJ21]. In practice however, the samples gathered rather correspond to a single, possibly infinite, trajectory of the system that we wish to control. This motivates our study of the full online setting where observations are only obtained by navigating in the MDP, that is by sequential choices of actions and following the transitions of the MDP.
Our contributions. [MP21] recently proposed an information-theoretical complexity analysis for MDPs in the case of access to a generative model. Here we extend their results to the online setting. Our main goal is to understand how the online learning scheme affects the sample complexity compared to the easier case where we have a generative model. A natural first step consists in understanding how the first order term T � log(1/δ) changes. Thus we only focus on the asymptotic regime δ → 0. Our key contributions can be summarized as follows:
• First, we adapt the lower bound of [MP21] to the online setting (Proposition 2). The new bound also writes as the value of a zero-sum two-player game between nature and the algorithm, where the loss function remains the same, but where the set of possible strategies for the algorithm is restricted to a subset Ω(M) of the simplex of dimension SA− 1. We refer to the constraints defining Ω(M) as the navigation constraints.
• We propose MDP-NaS, the first algorithm for the online setting1 with instance-dependent bounds on its sample complexity in the asymptotic regime δ → 0 (Theorem 6). A major challenge lies in the design of a sampling rule that guarantees that the sampling frequency of state-action pairs � Nsa(t)/t � s,a
converges to some target oracle allocation ω� ∈ Ω(M). Indeed, since we can no longer choose the next state of the agent, the tracking procedure which was developed by [GK16] for multi-armed bandits and used in [MP21] for MDPs with a generative model can no longer be applied in our setting. We propose a new sampling rule which performs exploration according to a mixture of the uniform policy and a plugin estimate of the oracle policy (the policy whose stationary state-action distribution is ω�) and prove that it satisfies the requirement above. The analysis of our sampling rule relies on an ergodic theorem for non-homogeneous Markov chains of independent interest (Proposition 12).
• We investigate, depending on the communication properties of the ground-truth instance M, what is the minimal forced-exploration rate in our sampling rule that guarantees the consistency of the plug-in estimator of the oracle policy. Our findings imply that when M is ergodic, an exploration rate as low as 1/ √ t is sufficient. However, when M is only assumed
to be communicating, one is obliged to resort to a much more conservative exploration rate of t− 1 m+1 , where m is a parameter defined in Lemma 4 that may scales as large as S − 1 in the worst case.
• Finally, our stopping rule represents the first implementation of the Generalized Likelihood Ratio test for MDPs. Notably, we circumvent the need to solve the max-min program of the lower bound exactly, and show how an upper bound of the best-response problem, such as the one derived in [MP21], can be used to perform a GLR test. This improves upon the sample complexity bound that one obtains using the KL-Ball stopping rule of [MP21] by at least a factor of 22.
1Before publication of this work, but after a preprint was available online, [WSJ21] proposed another algorithm with instance-dependent guarantees.
2Note that the stopping rule is independent of the sampling rule and thus can be used in both the generative and the online settings. Furthermore, one may even obtain an improved factor of 4 by using a deviation inequality for the full distribution of (reward, next-state) instead of a union bound of deviation inequalities for each marginal distribution.

heading: 1.1 Related work

text:
Minimax Best-Policy Identification. BPI in the online setting has been investigated recently by a number of works with minimax sample complexity bounds. In the case of episodic MDPs [KMDD+21], [MDJ+20] proposed algorithms that identify an ε-optimal policy at the initial state w.h.p. In contrast, in the case of infinite-horizon MDPs one is rather interested in finding a good policy at every state. Recent works provide convergence analysis for Q-learning [LWC+20b] or policy gradient algorithms [AHKS20], [FYAY21], [ZCA21]. Their results typically state that if the algorithm is fed with the appropriate hyperparameters, it can return an ε-optimal policy w.h.p. after collecting a polynomial number of samples. In practice, a pure exploration agent needs a stopping rule to determine when to halt the learning process. In particular, the question of how to tune the number of iterations of these algorithms without prior knowledge of the ground truth instance remains open.3
Generative Model. A large body of literature focuses on the so-called generative model, where in each step, the algorithm may query a sample (i.e., observe a reward and a next-state drawn from the rewards and transitions distributions respectively) from any given state-action pair [KS98],[KMN99], [EDMM06], [AMK13],[DTC13], [Wan17], [SWW+18], [ZKB19], [AKY20], [LWC+20a], [LCC+21], [MP21].
Instance-specific bounds. Instance-optimal algorithms for Best Arm Identification in multi armed bandits (MDPs with one state) have been obtained independently by [GK16],[Rus16]. Here, we extend their information-theoretical approach to the problem of Best Policy Identification in MDPs. More recently, [WSJ21] provided an algorithm for BPI in episodic MDPs with instance-specific sample complexity. A more detailed comparison with [WSJ21] can be found in Section 6.
Outline. The rest of the paper is organized as follows: After introducing the setting and giving some notation and definitions in Section 2, we derive in Section 3 a lower bound on the time required by any algorithm navigating the MDP until it is able to identify the best policy with probability at least 1− δ. The algorithm is presented in Section 4. Section 5 contains our main results along with a sketch of the analysis. Finally, in Section 6 we compare our results with MOCA, the only other algorithm (to the best of our knowledge) with problem-dependent guarantees in the online setting. Most technical results and proofs are given in the appendix.

heading: 2 Setting and notation

text:
Discounted MDPs. We consider infinite horizon MDPs with discount and finite state and action spaces S and A. Such an MDP M is defined through its transition and reward distributions pM(·|s, a) and qM(·|s, a) for all (s, a). For simplicity, qM(·|s, a) will denote the density of the reward distribution w.r.t. a positive measure λ with support included in [0, 1]. Specifically, pM(s�|s, a) denotes the probability of transitioning to state s� after playing action a at state s while R(s, a) is the random instantaneous reward that is collected. Finally, γ ∈ [0, 1) is a discounting factor. We look for an optimal control policy π� : S → A maximizing the long-term discounted reward: V πM(s) = EM,π[ �∞ t=0 γ
tR(st,π(st))], where EM,π denotes the expectation w.r.t the randomness in the rewards and the trajectory when the policy π is used. Classically, we denote by V �M the optimal value function of M and by Q�M the optimal Q-value function of M. Π�(M) = {π : S → A, V πM = V �M} denotes the set of optimal policies for M. Problem-dependent quantities. The sub-optimality gap of action a in state s is defined as Δsa = V � M(s) − Q�M(s, a). Let Δmin = mins,a�=π�(s) Δsa be the minimum gap and sp(V �M) = maxs,s� |V �M(s) − V �M(s�)| be the span of V �M. Finally, we introduce the variance of the value function in (s, a) as Varp(s,a)[V �M] = Vars�∼pM(.|s,a)[V � M(s �)].
Active pure exploration with fixed confidence. When M is unknown, we wish to devise a learning algorithm A identifying, from a single trajectory, an optimal policy as quickly as possible with some given level of confidence. Formally, such an algorithm consists of (i) a sampling rule, selecting in each round t in an adaptive manner the action at to be played; at depends on past observations, it
3Here we chose not to mention works that investigate the sample complexity in the PAC-MDP framework [Kak03]. Indeed, in this framework the sample complexity is rather defined as the the number of episodes where the algorithm does not play an ε-optimal policy. As explained in [DMKV21], this objective is closer to regret minimization than to pure exploration.
is FAt -measurable where FAt = σ(s0, a0, R0 . . . , st−1, at−1, Rt−1, st) is the σ-algebra generated by observations up to time t; (ii) a stopping rule τδ, a stopping time w.r.t. the filtration (FAt )t≥0, deciding when to stop collecting observations; (iii) a decision rule returning π̂�τδ an estimated optimal policy.
An algorithm A is δ-Probably Correct (δ-PC) over some set M of MDPs, if for any M ∈ M, it returns (in finite time) an optimal policy with probability at least 1 − δ. In this paper, we aim to devise a δ-PC algorithm A with minimal sample complexity EM,A[τδ]. We make the following assumption. Assumption 1. We consider the set M of communicating MDPs with a unique optimal policy.
We justify the above assumption as follows. (i) We restrict our attention to the case where M is communicating, for otherwise, if it is Multichain there would be a non-zero probability that the algorithm enters a subclass of states from which there is no possible comeback. In this case it becomes impossible to identify the global optimal policy4. (ii) About the uniqueness of the optimal policy, treating the case of MDPs with multiple optimal policies, or that of ε-optimal policy identification, requires the use of more involved Overlapping Hypothesis tests, which is already challenging in multiarmed bandits (MDPs with a single state) [GK19]. We will analyze how to remove this assumption in future work. Notation. Z � S × A is the state-action space. Σ � {ω ∈ RS×A+ : �
s,a ωsa = 1}, the simplex of dimension SA − 1. Nsa(t) denotes the number of times the state-action pair (s, a) has been visited up to the end of round t. We also introduce Ns(t) = � a∈A Nsa(t). Similarly, for a vector
ω ∈ Σ we will denote ωs � �
a∈A ωsa. For a matrix A ∈ Rn×m, the infinity norm is defined as �A�∞ � max1≤i≤n �m j=1 |ai,j |. The KL divergence between two probability distributions P and Q on some discrete space S is defined as: KL(P�Q) � �s∈S P (s) log( P (s) Q(s) ). For Bernoulli distributions of respective means p and q, the KL divergence is denoted by kl(p, q). For distributions over [0, 1] defined through their densities p and q w.r.t. some positive measure λ, the KL divergence is: KL(p�q) � �∞ −∞ p(x) log � p(x) q(x) � λ(dx). M denotes the set of communicating MDPs with a unique optimal policy. For two MDPs M,M� ∈ M, we say that M � M� if for all (s, a), pM(·|s, a) � pM�(·|s, a) and qM(·|s, a) � qM�(·|s, a). In that case, for any state (action pair) (s, a), we define the KL divergence of the distributions of the one-step observations under M and M� when starting at (s, a) as KLM|M�(s, a) � KL(pM(·|s, a)�pM�(·|s, a)) +KL(qM(·|s, a)�qM�(·|s, a)).

heading: 3 Sample complexity lower bound

text:
In this section, we first derive a lower bound on the expected sample complexity satisfied by any δ-PC algorithm. The lower bound is obtained as the solution of a non-convex optimization problem, as in the case where the learner has access to a generative model [MP21]. The problem has however additional constraints, referred to as the navigation constraints, due the fact that the learner has access to a single system trajectory. The expected sample complexity of an algorithm A is EM,A[τδ] = � s,a EM,A[Nsa(τδ)]. Lower bounds on the sample complexity are derived by identifying constraints that the various Nsa(τδ)’s need to satisfy so as to get a δ-PC algorithm. We distinguish here two kinds of constraints:
Information constraints. These are constraints on EM,A[Nsa(τδ)], so that the algorithm can learn the optimal policy with probability at least 1− δ. They are the same as those derived [MP21] when the learner has access to a generative model and are recalled in Lemma 9 in Appendix C.
Navigation constraints. Observations come from a single (but controlled) system trajectory which imposes additional constraints on the Nsa(τδ)’s. These are derived by just writing the ChapmanKolmogorov equations of the controlled Markov chain (refer to Appendix C for a proof). Lemma 1. For any algorithm A, and for any state s, we have:���EM,A[Ns(τδ)]− �
s�,a�
pM(s|s�, a�)EM,A[Ns�a�(τδ)] ��� ≤ 1. (1)
Putting all constraints together, we obtain the following sample complexity lower bound. 4Unless we modify the objective to finding the optimal policy in this subchain.
Proposition 2. Define the set of navigation-constrained allocation vectors:
Ω(M) = � ω ∈ Σ : ∀s ∈ S, ωs = �
s�,a�
pM(s|s�, a�)ωs�a� � .
Further define Alt(M) = {M� MDP : M � M�,Π�(M) ∩ Π�(M�) = ∅} the set of alternative instances. Then the expected sample complexity EM,A[τδ] of any δ-PC algorithm A satisfies:
lim inf δ→0 EM,A[τ ] log(1/δ) ≥ To(M), where To(M)−1 = sup ω∈Ω(M) T (M,ω)−1 (2)
and T (M,ω)−1 = inf
M�∈Alt(M)
�
s,a
ωsaKLM|M�(s, a). (3)
Remark 1. A common interpretation of change-of-measure lower bounds like the one above is the following: the optimization problem in the definition of To(M) can be seen as the value of a twoplayer zero-sum game between an algorithm which samples each state-action (s, a) proportionally to ωsa and an adversary who chooses an alternative instance M� that is difficult to distinguish from M under the algorithm’s sampling strategy. This suggests that an optimal algorithm should play the optimal allocation that solves the optimization problem (2) and, as a consequence, rules out all alternative instances as fast as possible. Remark 2. Note that compared to the lower bound of the generative setting in [MP21], the only change is in the set of sampling strategies that the algorithm can play, which is no longer equal to the entire simplex.

heading: 3.1 Proxy for the optimal allocation and the characteristic time

text:
As shown in [MP21], even without accounting for the navigation constraints, computing the characteristic time To(M) and in particular, the optimal allocation leading to it is not easy. Indeed, the sub-problem corresponding to computing T (M,ω)−1 is non-convex. This makes it difficult to design an algorithm that targets the optimal weights argmaxω∈Ω(M) T (M,ω)−1. Instead, we use a tractable upper bound of T (M,ω) from [MP21]: Lemma 3. (Theorem 1, [MP21]) For all vectors ω ∈ Σ, T (M,ω) ≤ U(M,ω), where5
U(M,ω) = max (s,a):a �=π�(s) Hsa ωsa + H�
Smin s
ωs,π�(s) , (4)
and    Hsa = 2 Δ2sa +max � 16Varp(s,a)[V � M] Δ2sa , 6 sp(V �M) 4/3 Δ 4/3 sa � , H� = 2S
[Δmin(1− γ)]2 +O
� S Δ2min(1− γ)3 � .
(5)
Using U(M,ω), we obtain the following upper bound on the characteristic time (2): To(M) ≤ Uo(M) � inf
ω∈Ω(M) U(M,ω). (6)
The advantages of the above upper bound Uo(M) are that: (i) it is a problem-specific quantity as it depends on the gaps and variances of the value function in M; (ii) the corresponding allocation (that solves (6)) can be easily computed, and hence targeted. Indeed, the optimization problem in (6) has convex objective and constraints. Therefore, we can use the projected subgradient-descent algorithm to compute
ω�(M) � argmin ω∈Ω(M) U(M,ω) = argmax ω∈Ω(M) U(M,ω)−1, (7)
which will be used in our algorithm as a proxy6 for argmaxω∈Ω(M) T (M,ω)−1. 5The exact definition of H� is given in Appendix C. 6Note that if we have access to an optimization oracle that, given a MDP M, returns the optimal allocation solution to (2), then we can replace ω�(M) by this optimal allocation. Our algorithm will then be asymptotically optimal up to a factor of 2.

heading: 4 Algorithm

text:
We propose MDP-NaS (MDP Navigate-and-Stop), a model-based algorithm that is inspired by the lower bound. The lower bound suggests that to identify the best policy in a sample-efficient manner, the algorithm must collect samples from state-action pair (s, a) proportionally to ω�sa(M). We propose two sampling rules which ensure that the former statement holds in the long term (see Section 4.1 and Theorem 7 for a rigorous formulation). Our sampling rules are combined with a Generalized Likelihood Ratio (GLR) test (or rather a proxy of the GLR test, see Section 4.2 for details), that stops as soon as we are confident that �π�t = π� with probability at least 1 − δ. The pseudo-code for MDP-NaS is given in Algorithm 1.
Algorithm 1: MDP Navigate and Stop (MDP-NaS) Input: Confidence level δ, ERGODIC boolean variable, communication parameter m or an
upper bound. 1 if ERGODIC then 2 Set (εt)t≥1 = (1/ √ t)t≥1. 3 else 4 Set (εt)t≥1 = (t− 1 m+1 )t≥1. 5 end 6 Set t ← 0 and Nsa(t) ← 0, for all (s,a). 7 Initialize empirical estimate �M0 by drawing an arbitrary MDP from M. 8 Compute �π�t ← POLICY-ITERATION(�Mt). 9 while Stopping condition (13) is not satisfied do 10 Compute ω�(�Mt) according to (7) and πo(�Mt) according to (8). 11 if t = 0 then 12 Play a0 ∼ Unif([|1, A|]). 13 else 14 Play at ∼ πt(.|st), where πt is determined by either (9) or (10). 15 end 16 Observe (Rt, st+1) ∼ q(.|st, at)⊗ p(.|st, at). 17 t ← t+ 1. 18 Update �Mt and (Nsa(t))s,a. 19 Compute �π�t ← POLICY-ITERATION(�Mt). 20 end
Output: Empirical optimal policy �π�τ .

heading: 4.1 Sampling rule

text:
We introduce a few definitions to simplify the presentation. Any stationary policy π induces a Markov chain on Z whose transition kernel is defined by Pπ((s, a), (s�, a�)) � P (s�|s, a)π(a�|s�). With some abuse of notation, we will use Pπ to refer to both the Markov chain and its kernel. We denote by πu the uniform random policy, i.e., πu(a|s) = 1/A for all pairs (s, a). Finally, we define the vector of visit-frequencies N(t)/t � � Nsa(t)/t � (s,a)∈Z .
In contrast with pure exploration in Multi-Armed Bandits and MDPs with a generative model where any allocation vector in the simplex is achievable, here the agent can only choose a sequence of actions and follow the resulting trajectory. Therefore, one might ask if the oracle allocation can be achieved by following a simple policy. A natural candidate is the oracle policy defined by
∀(s, a) ∈ Z, πo(a|s) � ω � sa
ω�s = ω�sa� b∈A ω � sb . (8)
It is immediate to check that ω� is the stationary distribution of Pπo . Denote by πo(M) the above oracle policy defined through ω�(M). Policy πo(M) is the target that we would like to play, but since the rewards and dynamics of M are unknown, the actions must be chosen so as to estimate consistently the oracle policy while at the same time ensuring that N(t)/t converges to ω�(M). The following two sampling rules satisfy these requirements.
D-Navigation rule: At time step t, the learner plays the policy
πt = εtπu + (1− εt)πo(�Mt), (9) C-Navigation rule: At time step t, the learner plays
πt = εtπu + (1− εt) t�
j=1
πo(�Mj)/t, (10)
where εt is a decreasing exploration rate to be tuned later. In the second case, the agent navigates using a Cesàro-mean of oracle policies instead of the current estimate of the oracle policy, which makes the navigation more stable.

heading: 4.1.1 Tuning the forced exploration parameter

text:
The mixture with the uniform policy7 helps the agent to explore all state-action pairs often enough in the initial phase. This is particularly necessary in the case where the empirical weight ω�sa(�Mt) of some state-action pair (s, a) is under-estimated, which may cause that this pair is left aside and hence the estimation never corrected. The next result in this section gives a tuning of the rate εt that ensures a sufficient forced exploration: Lemma 4. Let m be the maximum length of the shortest paths (in terms of number of transitions) between pairs of states in M: m � max(s,s�)∈S2 min{n ≥ 1 : ∃π : S → A, Pnπ (s, s�) > 0}. Then C-Navigation or D-Navigation with any decreasing sequence (εt)t≥1 such that ∀t ≥ 1, εt ≥ t− 1 m+1
satisfies: PM,A � ∀(s, a) ∈ Z, limt→∞ Nsa(t) = ∞ � = 1.
Remark 3. When the parameter m is unknown to the learner, one can replace it by its worst case value mmax = S − 1. However, when prior knowledge is available, using a faster-decreasing sequence εt = t− 1 m+1 instead of t− 1 S can be useful to accelerate convergence, especially when the states of M are densely connected (m � S − 1).
Minimal exploration rate: Communicating MDPs. The forced exploration rate t− 1S vanishes quite slowly. One may wonder if this rate is necessary to guarantee sufficient exploration in communicating MDPs: the answer is yes in the worst case, as the following example shows. Consider a variant of the classical RiverSwim MDP with state (resp. action) space S = [|1, S|], (resp. A = {LEFT1, LEFT2, RIGHT}). LEFT1 and LEFT2 are equivalent actions inducing the same rewards and transitions. After playing RIGHT the agent makes a transition of one step to the right, while playing LEFT1 (or LEFT2) moves the agent all the way back to state 1. The rewards are null everywhere but in states {1, S} where R(1, LEFT1), R(1, LEFT2) are equal to 0.01 almost surely and R(S, RIGHT) is Bernoulli with mean 0.02.
When γ is close to 1, the optimal policy consists in always playing RIGHT so as to reach state S and stay there indefinitely. Now suppose that the agent starts at s = 1 and due to the small probability of observing the large reward in state S, she underestimates the value of this state in the first rounds and focuses on distinguishing the best action to play in state 1 among {LEFT1, LEFT2}. Under this scenario she ends up playing a sequence of policies that scales like πt = 2εtπu + (1− 2εt)(LEFT1 + LEFT2)/28. This induces the non-homogeneous Markov Chain depicted in Figure 1. For the exploration rate εt = t−α, we show that if the agent uses any α > 1S−1 , with non-zero probability she will visit state S only a finite number of times. Therefore she will fail to identify the optimal policy for small values of the confidence level δ. The proof is deferred to Appendix D.
Minimal exploration rate: Ergodic MDPs. For such MDPs, we can select εt = 1/tα where α < 1 without compromising the conclusion of Lemma 4. The proof is deferred to Appendix D.

heading: 4.2 Stopping rule

text:
To implement a GLR test, we define �M�(t), the likelihood of the observations under some MDP M� � M: �M�(t) = �t−1 k=0 pM�(sk+1|sk, ak)qM�(Rk|sk, ak), where at step k the algorithm is in
7Our results still hold if πu is replaced by any other policy π which has an ergodic kernel. In practice, this can be helpful especially when we have prior knowledge of a fast-mixing policy π.
8Modulo a re-scaling of εt by a constant factor of 1/2.
state sk, plays action ak and observes the reward Rk and sk+1 (the next state). Performing a GLR test in step t consists in computing the optimal policy �π�t for the estimated MDP �Mt and in comparing the likelihood of observations under the most likely model where �π�t is optimal to the likelihood under the most likely model where �π�t is sub-optimal. Following the standardized form of the GLR for multi-armed bandits in [DKM19] we write:
G�π�t (t) = log
sup M�:�π�t ∈Π�(M�) �M�(t)
sup M�:�π�t /∈Π�(M�)
�M�(t) = log
��Mt(t)
sup M�∈Alt( �Mt)
�M�(t) = inf M�∈Alt( �Mt) log
��Mt(t)
�M�(t)
= inf M�∈Alt( �Mt)
�
(s,a)∈Z Nsa(t)
� KL(�qs,a(t), qM�(s, a)) + KL(�ps,a(t), pM�(s, a)) � (11)
= t T � �Mt,N(t)/t �−1 . (12)
The hypothesis (�π�t �= π�) is then rejected as soon as the ratio of likelihoods becomes greater than the threshold β(t, δ), properly tuned to ensure that the algorithm is δ-PC. Note that the likelihood ratio G�π�t (t) itself can be difficult to compute for MDPs, since it is equivalent to solving (3), we lower bound it using (12) and Lemma 3. This leads to the following proposition: Proposition 5. Define the random thresholds for the transitions and rewards respectively:
βp(t, δ) � log(1/δ) + (S − 1) �
(s,a)
log � e � 1 +Nsa(t)/(S − 1) ��
βr(t, δ) � SA ϕ � log(1/δ)/SA � + 3 �
s,a
log � 1 + log(Nsa(t)) �
where ϕ(x) ∼ ∞ x+ log(x) is defined in the appendix. Then the stopping rule:
τδ � inf � t ≥ 1 : t U � �Mt,N(t)/t �−1 ≥ βr(t, δ/2) + βp(t, δ/2) � (13)
is δ-PC, i.e., P(τδ < ∞, �π�τδ �= π�) ≤ δ.

heading: 5 Main results and sample complexity analysis

text: First we state our main results, which take the form of asymptotic upper bounds on the sample complexity of MDP-NaS, under a slightly more conservative exploration rate than in Lemma 4. Then we present the most important ingredients in their proof. The complete proof is provided in Appendix F. Theorem 6. Using the C-Navigation sampling rule with εt = t− 1 2(m+1) and the stopping rule (13): (i) MDP-NaS stops almost surely and its stopping time satisfies P � lim supδ→0 τδ log(1/δ) ≤ 2Uo(M) � = 1, where Uo(M) was defined in (6); (ii) the stopping time of MDP-NaS has a finite expectation for all δ ∈ (0, 1), and lim supδ→0 E[τδ] log(1/δ) ≤ 2Uo(M).

heading: 5.1 Proof sketch

text:
Concentration of empirical MDPs: The starting point of our proof is a concentration event of the empirical estimates �Mt around M. For ξ > 0 and T ≥ 1, we define C1T (ξ) = �T
t=T 1/4
���� �Mt −M ��� ≤ ξ, ���πo(�Mt)− πo(M) ��� ∞ ≤ ξ �
, where �.� is a semi-norm on MDPs. Then we prove in Lemma 18 that C1T (ξ) holds with high probability in the sense that for all T ≥ 1:
P � C1T (ξ) � ≥ 1−O � 1/T 2 � . (14)
For this purpose we derive, for all pairs (s, a), a lower bound on Nsa(t) stating that9: P � ∀(s, a) ∈ Z, ∀t ≥ 1, Nsa(t) ≥ (t/λα)1/4 − 1 � ≥ 1 − α where λα ∝ log2(1 + SA/α) is a parameter that depends on the mixing properties of M under the uniform policy. These lower bounds on Nsa(t) w.h.p. contrast with their deterministic equivalent obtained for C-tracking in [GK16].
Concentration of visit-frequencies: Before we proceed, we make the following assumption.
Assumption 2. Pπu is aperiodic10.
Under Assumptions 1 and 2 the kernel Pπu , and consequently also Pπo , becomes ergodic. Hence the iterates of Pπo converge to ω�(M) at a geometric speed. Also note that the Markov chains induced by playing either of our sampling rules are non-homogeneous, with a sequence of kernels (Pπt)t≥1 that is history-dependent. To tackle this difficulty, we adapt a powerful ergodic theorem (see Proposition 12 in the appendix) from [FMP11] originally derived for adaptive Markov Chain Monte-Carlo (MCMC) algorithms to get the following result.
Theorem 7. Using the C-Navigation or D-Navigation we have: lim t→∞ N(t)/t = ω�(M) almost surely.
Lemma 4 and Theorem 7 combined prove Theorem 6 (i) in a straightforward fashion. The proof of Theorem 6 (ii) is more involved. Again, we adapt the proof method from [FMP11] to derive a finite-time version of Proposition 12 which results into the following proposition.
Proposition 8. Under C-Navigation, for all ξ > 0, there exists a time Tξ such that for all T ≥ Tξ, all t ≥ T 3/4 and all functions f : Z −→ �+, we have:
P ����� �t k=1 f(sk, ak)
t − E(s,a)∼ω� [f(s, a)]
���� ≥ Kξ �f�∞ ξ ����C1T (ξ) � ≤ 2 exp � − tξ2 � .
where ξ �→ Kξ is a mapping with values in (1,∞) such that lim supξ→0 Kξ < ∞.
Now define C2T (ξ) = �T t=T 3/4 ���N(t)/t − ω�(M) �� ≤ Kξ ξ � . Then Proposition 8 and Eq. (14) combined imply that for T large enough, the event C1T (ξ) ∩ C2T (ξ) holds w.h.p. so that the expected stopping time is finite on the complementary event: E[τδ�{C1T (ξ) ∪ C2T (ξ)}] < ∞. Now given the asymptotic shape of the thresholds: βr(t, δ/2) + βp(t, δ/2) ∼
δ→0 2 log(1/δ), we may informally
write:
E � τδ�{C1T (ξ) ∩ C2T (ξ)} � �
δ→0 2 log(1/δ) sup (M�,ω�)∈Bξ Uo
� M�,ω� � ,
where Bξ = {(M�,ω�) : �M� −M� ≤ ξ, �ω� − ω�(M)�∞ ≤ Kξ ξ}. Taking the limits when δ and ξ go to zero respectively concludes the proof.
9Using the method in our proof one can derive a lower bound of the type tζ for any ζ < 1/2 and any exploration rate εt = t−θ with θ < 1/(m+ 1). We chose θ = 12(m+1) and ζ = 1/4 because they enable us to have an explicit formula for λα. See Lemma 11 in the appendix.
10This assumption is mild as it is enough to have only one state s̃ and one action ã such that PM(s̃|s̃, ã) > 0 for it to be satisfied. Furthermore, Assumptions 1 and 2 combined are still less restrictive than the usual ergodicity assumption, which requires that the Markov chains of all policies are ergodic.

heading: 6 Comparison with MOCA

text:
Recall from Lemma 3 and Theorem 6 that our sample complexity bound writes as:
O �
inf ω∈Ω(M) max (s,a):a �=π�(s)
1 + Varp(s,a)[V � M]
ωsaΔ2sa +
1
min s
ωs,π�(s)Δ 2 min(1− γ)3
� log(1/δ).
Hence, in the asymptotic regime δ → 0, MDP-NaS finds the optimal way to balance exploration between state-action pairs proportionally to their hardness: (1+Varp(s,a)[V �M])/Δ 2 sa for sub-optimal pairs (resp. 1/Δ2min(1− γ)3 for optimal pairs). After a preprint of this work was published, [WSJ21] proposed MOCA, an algorithm for BPI in the episodic setting. MOCA has the advantage of treating the more general case of ε-optimal policy identification with finite-time guarantees on its sample complexity. The two papers have different and complementary objectives but one can compare with their bound for exact policy identification, i.e when ε < ε�11, in the asymptotic regime δ → 0. In this case, by carefully inspecting the proofs of [WSJ21], we see that MOCA’s sample complexity writes as12:
O � H�
h=1
inf ω∈Ω(M) max s,a�=π�(s)
H2
ωsa(h)Δsa(h)2
� log(1/δ) +
polylog(S,A,H, log(ε∗)) log3(1/δ) ε∗
where H is the horizon and Δsa(h) is the sub-optimality gap of (s, a) at time step h. We make the following remarks about the bounds above:
1. MOCA only pays the cost of worst-case visitation probability multiplied by the gap of the corresponding state min
s,a�=π�(s) ωsaΔ
2 sa. Instead, MDP-NaS pays a double worst-case cost
of the smallest visitation probability multiplied by the minimum gap mins ωs,π�(s)Δ2min. As pointed out by [WSJ21] the former scaling is better, especially when the state where the minimum gap is achieved is different from the one that is hardest to reach. This is however an artefact of the upper bound in Lemma 3 that MDP-NaS uses as a proxy for the characteristic time. Using a more refined bound, or an optimization oracle that solves the best-response problem, one can remove this double worst-case dependency.
2. The sample complexity of MOCA divided by log(1/δ) still explodes when δ goes to zero, contrary to MDP-NaS’s bound.
3. The sample complexity of MDP-NaS is variance-sensitive for sub-optimal state-action pairs, while MOCA’s bound depends on a worst-case factor of H2. Indeed as the rewards are in [0, 1], we always have V �M ≤ H and Varp(s,a)[V �M] ≤ H2 in the episodic setting.
We conclude this section by noting that MDP-NaS has a simple design and can easily be implemented.

heading: 7 Conclusion

text:
To the best of our knowledge, this paper is the first to propose an algorithm with instance-dependent sample complexity for Best Policy identification (BPI) in the full online setting. Our results are encouraging as they show: 1) How the navigation constraints of online RL impact the difficulty of learning a good policy, compared to the more relaxed sampling schemes of Multi-Armed Bandits and MDPs with a generative model. 2) That, provided access to an optimization oracle that solves the information-theoretical lower bound (resp. some convex relaxation of the lower bound), asymptotic optimal (resp. near-optimal) sample complexity is still possible through adaptive control of the trajectory. This opens up exciting new research questions. First, it is intriguing to understand how the mixing times -and not just the stationary distributions- of Markov chains induced by policies impact the sample complexity of BPI in the moderate confidence regime. A second direction would be to extend our contributions to the problem of finding an ε-optimal policy, which is of more practical interest than identifying the best policy.
11ε� is defined in their work as the threshold value for ε such that the only ε-optimal policy is the best policy. However, when the objective is to find the optimal policy, it is not clear from their paper how one can determine such a value of ε without prior knowledge of the ground truth instance.
12The log3(1/δ) term comes from the sample complexity of their sub-routine FINDEXPLORABLESETS.
Broader Impact This paper tries to advance our theoretical understanding of the sample complexity of finding a good policy in Markov Decision Processes, which can be interesting for both theoreticians and practitioners. However, this paper is not oriented towards a specific application, so a wider broader impact discussion is not applicable.
Acknowledgments and Disclosure of Funding The authors would like to thank the anonymous reviewers whose comments and questions helped improve the clarity of this manuscript. A. Proutiere’s research is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. A. Garivier and A. Al Marjani acknowledge the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d’Avenir (ANR-16IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020).

title: Navigating to the Best Policy in Markov Decision Processes