16 papers · 1 filter
Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
Denis Belomestny, Alexey Naumov, Sergey Samsonov
In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every…
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…
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…
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…
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…