9 papers
Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
Rahul Singh, Vivek S. Borkar, Eric Moulines
We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contrac…
Refined Analysis of Entropy-Regularized Actor-Critic
Safwan Labbi, Paul Mangold, Daniil Tiapkin +1
In this paper, we study the role of the critic in actor--critic for entropy-regularized, finite, discounted environments. We establish that, when the critic is exact, using the lat…
Uniform Diffusion Models Revisited: Leave-One-Out Denoiser and Absorbing State Reformulation
Samson Gourevitch, Yazid Janati, Dario Shariatian +4
Discrete diffusion models are often trained through clean-data prediction, but the prediction can be used in different ways to define the reverse dynamics. In Masked Diffusion Mode…
Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
Ilya Levin, Maksim Shuklin, Eric Moulines +2
In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated Gaussian approximations for LSA th…
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…
Policy Gradient Methods for Non-Markovian Reinforcement Learning
Avik Kar, Siddharth Chandak, Rahul Singh +4
We study policy gradient methods for reinforcement learning in non-Markovian decision processes (NMDPs), where observations and rewards depend on the entire interaction history. To…
High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
Avik Kar, Siddharth Chandak, Rahul Singh +3
We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. T…
Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
Rahul Singh, Siddharth Chandak, Eric Moulines +2
We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We fi…
Inexact subgradient methods for semialgebraic functions
Jérôme Bolte, Tam Le, Éric Moulines +1
Motivated by the extensive application of approximate gradients in machine learning and optimization, we investigate inexact subgradient methods subject to persistent additive erro…