12 papers
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…
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…
Last-Iterate Guarantees for Learning in Co-coercive Games
Siddharth Chandak, Ramanan Tamizholi, Nicholas Bambos
We establish finite-time last-iterate guarantees for vanilla stochastic gradient descent in co-coercive games under noisy feedback. This is a broad class of games that is more gene…
Choose Your Battles: Distributed Learning Over Multiple Tug of War Games
Siddharth Chandak, Ilai Bistritz, Nicholas Bambos
Consider players and games taking place simultaneously. Each of these games is modeled as a Tug-of-War (ToW) game where increasing the action of one player decreases the re…
Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
Siddharth Chandak, Anuj Yadav, Ayfer Ozgur +1
Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martinga…
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…