We study the problem of best-arm identification with fixed confidence in stochastic linear bandits. The objective is to identify the best arm with a given level of certainty while minimizing the sampling budget. We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds, asymptotically almost surely and in expectation. The algorithm relies on an arm sampling rule that tracks an optimal proportion of arm draws, and that remarkably can be updated as rarely as we wish, without compromising its theoretical guarantees. Moreover, unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms. Experimental results suggest that our algorithm significantly outperforms existing algorithms. The paper further provides a first analysis of the best-arm identification problem in linear bandits with a continuous set of arms.

This paper establishes problem-specific sample complexity lower bounds for linear system identification problems. The sample complexity is defined in the PAC framework: it corresponds to the time it takes to identify the system parameters with prescribed accuracy and confidence levels. By problem-specific, we mean that the lower bound explicitly depends on the system to be identified (which contrasts with minimax lower bounds), and hence really captures the identification hardness specific to the system. We consider both uncontrolled and controlled systems. For uncontrolled systems, the lower bounds are valid for any linear system, stable or not, and only depend on the system finite-time controllability gramian. A simplified lower bound depending on the spectrum of the system only is also derived. In view of recent finite-time analysis of classical estimation methods (e.g. ordinary least squares), our sample complexity lower bounds are tight for many systems. For controlled systems, our lower bounds are not as explicit as in the case of uncontrolled systems, but could well provide interesting insights into the design of control policy with minimal sample complexity. 

We present a new finite-time analysis of the estimation error of the Ordinary Least Squares (OLS) estimator for stable linear time-invariant systems. We characterize the number of observed samples (the length of the observed trajectory) sufficient for the OLS estimator to be (?, d)-PAC, i.e., to yield an estimation error less than ? with probability at least 1 - d. We show that this number matches existing sample complexity lower bounds [1], [2] up to universal multiplicative factors (independent of (?, d) and of the system). This paper hence establishes the optimality of the OLS estimator for stable systems, a result conjectured in [1]. Our analysis of the performance of the OLS estimator is simpler, sharper, and easier to interpret than existing analyses. It relies on new concentration results for the covariates matrix.

We investigate the linear system identification problem in the so-called fixed budget and fixed confidence settings. In the fixed budget setting, the learner aims at estimating the state transition matrix A from a random system trajectory of fixed length, whereas in the fixed confidence setting, the learner also controls the length of the observed trajectory – she can stop when she believes that enough information has been gathered. For both settings, we analyze the sample complexity in the probably approximately correct (PAC) framework defined as the length of the observed trajectory required to identify the system parameters with prescribed accuracy and confidence levels (ε,δ) . In the fixed budget setting, we first establish problem-specific sample complexity lower bounds. We then present a finite-time analysis of the estimation error of the least-squares estimator (LSE) for stable systems, and show that in the high-accuracy regime, the sample complexity of the LSE matches our lower bounds. Our analysis of the LSE is sharper and easier to interpret than existing analyzes, and relies on novel concentration results for the covariates matrix. In the fixed confidence setting, in addition to the estimation objective, the learner also has to decide when to stop the collection of observations. The sample complexity then corresponds to the expected stopping time. For this setting, we also provide problem specific sample complexity lower bounds. We also propose a stopping rule which combined to the LSE enjoys a sample complexity that matches our lower bounds in the high-accuracy and high-confidence regime.

We consider the problem of online learning in Linear Quadratic Control systems whose state transition and state-action transition matrices A and B may be initially unknown. We devise an online learning algorithm and provide guarantees on its expected regret. This regret at time T is upper bounded (i) by (O) over tilde((d(u) + d(x))root d(x)T) when A and B are unknown, (ii) by (O) over tilde (d(x)(2) log(T)) if only A is unknown, and (iii) by (O) over tilde (d(x)(d(u) + d(x))log(T)) if only B is unknown and under some mild non-degeneracy condition (d(x) and d(u) denote the dimensions of the state and of the control input, respectively). These regret scalings are minimal in T, d(x) and d(u) as they match existing lower bounds in scenario (i) when d(x) <= d(u) (Simchowitz and Foster, 2020), and in scenario (ii) (Lai, 1986). We conjecture that our upper bounds are also optimal in scenario (iii) (there is no known lower bound in this setting). Existing online algorithms proceed in epochs of (typically exponentially) growing durations. The control policy is fixed within each epoch, which considerably simplifies the analysis of the estimation error on A and B and hence of the regret. Our algorithm departs from this design choice: it is a simple variant of certainty-equivalence regulators, where the estimates of A and B and the resulting control policy can be updated as frequently as we wish, possibly at every step. Quantifying the impact of such a constantly-varying control policy on the performance of these estimates and on the regret constitutes one of the technical challenges tackled in this paper.

We investigate the problem of best policy identification in discounted linear Markov Decision Processes in the fixed confidence setting under a generative model. We first derive an instance-specific lower bound on the expected number of samples required to identify an ε-optimal policy with probability 1−δ. The lower bound characterizes the optimal sampling rule as the solution of an intricate non-convex optimization program, but can be used as the starting point to devise simple and near-optimal sampling rules and algorithms. We devise such algorithms. One of these exhibits a sample complexity upper bounded by (d/(ε+Δ)² (log(1/δ)+d)) where Δ denotes the minimum reward gap of sub-optimal actions and d is the dimension of the feature space. This upper bound holds in the moderate-confidence regime (i.e., for all δ), and matches existing minimax and gap-dependent lower bounds. We extend our algorithm to episodic linear MDPs.

We consider the problem of model estimation in episodic Block MDPs. In these MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are interested in estimating the latent state decoding function (the mapping from the observations to latent states) based on data generated under a fixed behavior policy. We derive an information-theoretical lower bound on the error rate for estimating this function and present an algorithm approaching this fundamental limit. In turn, our algorithm also provides estimates of all the components of the MDP. We apply our results to the problem of learning near-optimal policies in the reward-free setting. Based on our efficient model estimation algorithm, we show that we can infer a policy converging (as the number of collected samples grows large) to the optimal policy at the best possible rate. Our analysis provides necessary and sufficient conditions under which exploiting the block structure yields improvements in the sample complexity for identifying near-optimal policies. When these conditions are met, the sample complexity in the minimax reward-free setting is improved by a multiplicative factor , where  is the number of possible contexts.