24 papers
On Gaussian approximation for entropy-regularized Q-learning with function approximation
Artemy Rubtsov, Rahul Singh, Eric Moulines +2
In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak--Ruppert averaged iterates generated by entropy-regularized asynchronous Q-le…
Gaussian Approximation for Asynchronous Q-learning
Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov +1
In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm…
Schrödinger bridge problem via empirical risk minimization
Denis Belomestny, Alexey Naumov, Nikita Puchkin +1
We study the Schrödinger bridge problem when the endpoint distributions are available only through samples. Classical computational approaches estimate Schrödinger potentials via S…
Statistical analysis of Inverse Entropy-regularized Reinforcement Learning
Denis Belomestny, Alexey Naumov, Artemy Rubtsov +1
Inverse reinforcement learning aims to infer the reward function that explains expert behavior observed through trajectories of state--action pairs. A long-standing difficulty in c…
Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
Bogdan Butyrin, Eric Moulines, Alexey Naumov +3
In this paper, we refine the Berry-Esseen bounds for the multivariate normal approximation of Polyak-Ruppert averaged iterates arising from the linear stochastic approximation (LSA…
High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
Ilya Levin, Alexey Naumov, Sergey Samsonov
In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We foc…
Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
Bogdan Butyrin, Artemy Rubtsov, Alexey Naumov +2
In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale diff…
Tight Bounds for Schrödinger Potential Estimation in Unpaired Data Translation
Nikita Puchkin, Denis Suchkov, Alexey Naumov +1
Modern methods of generative modelling and unpaired data translation based on Schrödinger bridges and stochastic optimal control theory aim to transform an initial density to a tar…
Sample complexity of Schrödinger potential estimation
Nikita Puchkin, Iurii Pustovalov, Yuri Sapronov +3
We address the problem of Schrödinger potential estimation, which plays a crucial role in modern generative modelling approaches based on Schrödinger bridges and stochastic optimal…
Adaptive Destruction Processes for Diffusion Samplers
Timofei Gritsaev, Nikita Morozov, Kirill Tamogashev +5
This paper explores the challenges and benefits of a trainable destruction process in diffusion samplers -- diffusion-based generative models trained to sample an unnormalised dens…
Statistical inference for Linear Stochastic Approximation with Markovian Noise
Sergey Samsonov, Marina Sheshukova, Eric Moulines +1
In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise…
A note on concentration inequalities for the overlapped batch mean variance estimators for Markov chains
Eric Moulines, Alexey Naumov, Sergey Samsonov
In this paper, we study the concentration properties of quadratic forms associated with Markov chains using the martingale decomposition method introduced by Atchadé and Cattaneo (…
Proximal Point Nash Learning from Human Feedback
Daniil Tiapkin, Daniele Calandriello, Denis Belomestny +5
Traditional Reinforcement Learning from Human Feedback (RLHF) often relies on reward models, frequently assuming preference structures like the Bradley--Terry model, which may not…
Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
Marina Sheshukova, Sergey Samsonov, Denis Belomestny +4
In this paper, we establish the non-asymptotic validity of the multiplier bootstrap procedure for constructing the confidence sets using the Stochastic Gradient Descent (SGD) algor…
Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
Marina Sheshukova, Denis Belomestny, Alain Durmus +3
We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works sugge…
A New Bound on the Cumulant Generating Function of Dirichlet Processes
Pierre Perrault, Denis Belomestny, Pierre Ménard +4
In this paper, we introduce a novel approach for bounding the cumulant generating function (CGF) of a Dirichlet process (DP) , using superadditivity. In par…
Improving GFlowNets with Monte Carlo Tree Search
Nikita Morozov, Daniil Tiapkin, Sergey Samsonov +2
Generative Flow Networks (GFlowNets) treat sampling from distributions over compositional discrete spaces as a sequential decision-making problem, training a stochastic policy to c…
Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
Sergey Samsonov, Eric Moulines, Qi-Man Shao +2
In this paper, we obtain the Berry-Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorith…
SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
Paul Mangold, Sergey Samsonov, Safwan Labbi +4
In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local t…
Model-free Posterior Sampling via Learning Rate Randomization
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +6
In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the bes…
Demonstration-Regularized RL
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +5
Incorporating expert demonstrations has empirically helped to improve the sample efficiency of reinforcement learning (RL). This paper quantifies theoretically to what extent this…
Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
Sergey Samsonov, Daniil Tiapkin, Alexey Naumov +1
In this paper we consider the problem of obtaining sharp bounds for the performance of temporal difference (TD) methods with linear function approximation for policy evaluation in…
Generative Flow Networks as Entropy-Regularized RL
Daniil Tiapkin, Nikita Morozov, Alexey Naumov +1
The recently proposed generative flow networks (GFlowNets) are a method of training a policy to sample compositional discrete objects with probabilities proportional to a given rew…
UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithms
Denis Belomestny, Ilya Levin, Alexey Naumov +1
Policy evaluation is an important instrument for the comparison of different algorithms in Reinforcement Learning (RL). However, even a precise knowledge of the value function $V^π…