Satellite workshop 14 November

Alexandre Proutiere (KTH Royal Institute of Technology)

Efficient methods for low-rank reinforcement learning
We consider the problem of learning an ε-optimal policy in controlled dynamical systems with low-rank latent structure. For this problem, we present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. In the latter, the algorithm estimates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the leverage scores of its rows and columns. These scores are then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to complete the matrix estimation using a CUR-like method. For this leveraged matrix estimation procedure, we establish entry-wise guarantees that remarkably, do not depend on the coherence of the matrix but on its spikiness instead. S: For this leveraged matrix estimation procedure, we establish entry-wise guarantees that remarkably, do not depend explicitly on the coherence

of the matrix but only on its spikiness. These guarantees imply that LoRa-PI learns an ε-optimal policy using O( (S+A )poly(1−γ)ε2 ) samples where S (resp. A) denotes the number of states (resp. actions) and γ the discount factor. Our algorithm achieves this order-optimal (in S, A and ε) sample complexity under milder conditions than those assumed in previously proposed approaches.

Collaborations with Stefan Stojanovic and Yassir Jedra

Rui Castro (Eindhoven University of Technology)

Detecting a (late) changepoint in the preferential attachment model
Motivated by the problem of detecting a change in the evolution of a network, we consider the preferential attachment random graph model with a time-dependent attachment function. We frame the detection task as a hypothesis testing problem where the null hypothesis is a preferential attachment model with $n$ vertices and a constant affine attachment with parameter $\delta_0$, and the alternative hypothesis is a preferential attachment model where the affine attachment parameter changes from $\delta_0$ to $\delta_1$ at an unknown changepoint time $\tau_n$. For our analysis we focus on a scenario where one only sees the final network realization (and not its evolution), and the changepoint occurs “late”, namely $\tau_n = n − cn^\gamma$ with $c \geq 0$ and $\gamma\in(0,1)$. This corresponds to the relevant scenario where we aim to detect the changepoint shortly after it has happened. We present two asymptotically powerful tests that are able to distinguish between the null and alternative hypothesis when $\gamma>1/2$. The first test requires knowledge of $\delta_0$, while the second test is significantly more involved, and does not require the knowledge of $\delta_0$ while still achieving the same performance guarantees. Furthermore, we determine the asymptotic distribution of the test statistics, which allows us to easily calibrate the tests in practice. Finally, we conjecture that in the setting considered there are no powerful tests when $\gamma<1/2$ (a preprint with a partial proof of the conjecture has recently been published by Kaddouri, Naulet and Gassiat). Our theoretical results are complemented with numerical evidence that illustrates the finite sample characteristics of the proposed procedures.

Based on joint work with Gianmarco Bet, Kay Bogerd, and Remco van der Hofstad

Jiesen Wang (University of Amsterdam)

Estimation of on- and off-time distributions in dynamic random graphs
In this presentation we consider a dynamic Erdös-Rényi graph in which edges, according to an alternating renewal process, change from present to absent and vice versa. The objective is to estimate the on- and off-time distributions while only observing the aggregate number of edges. This inverse problem is dealt with, in a parametric context, by setting up an estimator based on the method of moments. We provide conditions under which the estimator is asymptotically normal, and we point out how the corresponding covariance matrix can be identified. It is also demonstrated how to adapt the estimation procedure if alternative subgraph counts are observed, such as the number of wedges or triangles. We finally illustrate how the method can be applied to to the Chung-Lu model, which is more general in the sense that not all edges behave statistically identically. 

Paulo Serra (Vrije Universiteit Amsterdam)

Dimension Estimation Using Random Connection Models
Information about intrinsic dimension is crucial to perform dimensionality reduction, com- press information, design efficient algorithms, and do statistical adaptation. In this presentation we propose an estimator for the intrinsic dimension of a data set. The estimator is based on binary neighbourhood information about the observations in the form of two adjacency matrices, and does not require any explicit distance information. The underlying graph is modelled according to a subset of a specific random connection model, sometimes referred to as the Poisson blob model. Computationally the estimator scales like nlogn, and we specify its asymptotic distribution and rate of convergence. A simulation study on both real and simulated data shows that our approach compares favourably with some competing methods from the literature, including approaches that rely on distance information.

Shota Gugushvili (Wageningen University & Research)

Nonparametric Bayesian volatility estimation for gamma-driven stochastic differential equations
We consider a nonparametric Bayesian approach to estimation of the volatility function of a stochastic differential equation driven by a gamma process. The volatility function is modelled a priori as piecewise constant, and we specify a gamma prior on its values. This leads to a straightforward MCMC procedure for posterior inference. We give theoretical performance guarantees (minimax optimal contraction rates for the posterior) for the Bayesian estimate in terms of the regularity of the unknown volatility function. We illustrate the method on synthetic and real data examples.

The talk is based on the joint work with D. Belomestny, M. Schauer, and P. Spreij.

Liron Ravner (University of Haifa)

Indirect estimation in queueing systems
In many queueing systems, direct observation of key quantities such as arrival rates, job sizes, or customer decision-making is often challenging or impossible. This talk will review several methods of indirect estimation that allow us to infer these unobserved inputs from observable outputs or performance measures. Three examples will be discussed in detail: (1) estimating the input process to a queue based on output data and workload observations, (2) inferring user properties, such as patience parameters or service values, in queues with strategic customers, and (3) statistical inference using Little’s law for systems with arrival rate uncertainty. Each of these problems will be related to classical statistical challenges, including censored data, deconvolution of noise, and the decomposition of compound processes. Constructing ‘good’ estimators requires combining these fundamental techniques with queueing-theoretic analysis of the underlying stochastic processes. Our goal is to provide estimators with provable asymptotic guarantees, such as consistency, asymptotic normal errors, or bounds on convergence rates in the context of nonparametric methods. The methods and challenges for this type of analysis will be highlighted through the examples.