14 papers
Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach
Siddharth Chandak
We establish mean-square and concentration bounds for stochastic approximation (SA) with arbitrary norm contractive mappings, under a multiplicative noise model where the noise may…
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…
Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
Siddharth Chandak
Two-time-scale stochastic approximation algorithms are iterative methods used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of the…