We are interested in synthesizing and analyzing stochastic approximation algorithms for distributed optimization and game-theoretic learning. How quickly can a constant step size stochastic approximation track a time varying parameter or more generally, the equilibria of a time varying game? Stochastic averaging theory is the main tool that we use to analyze such algorithms. One of our major results is that if the parameter jumps according to a Markov chain with slow transition matrix, then the asymptotic behavior of the stochastic approximation converges to a switched-Markovian ordinary differential equation or differential inclusion.
Related Papers
Stochastic Gradient Algorithms & Weak convergence; Reinforcement Learning
- Namvar, V. Krishnamurthy, G. Yin, Adaptive Search Algorithms for Discrete Stochastic Optimization: A Smooth Best-Response Approach, IEEE Transactions Automatic Control, 2017.
- Hamdi, V. Krishnamurthy, G. Yin, Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph, IEEE Transactions Information Theory, 2014.
- Namvar, V. Krishnamurthy and G. Yin, Distributed Tracking of Correlated Equilibria in Regime Switching Noncooperative Games, IEEE Transactions Automatic Control, pp.2435–2450, 2013.
-
O. Namvar. V. Krishnamurthy and G. Yin, Distributed Energy-Aware Diffusion Least Mean Squares: Game-Theoretic Learning, IEEE Journal Selected Topics in Signal Processing, Vol.7, No.5, pp.821–836, 2013.
- V. Krishnamurthy, F. Vazquez-Abad, Gradient Based Policy Optimization of Constrained Unichain Markov Decision Processes, Festschrift for Robert Elliott’s 70th Birthday, World Scientific, 2012.
- V. Krishnamurthy, K. Topley and G. Yin, Consensus Formation in a two-time-scale Markovian System, SIAM Journal Multiscale Modeling and Simulation, Vol.7, No.4, pp.1898–1927, 2009.
-
G. Yin, C. Ion and V. Krishnamurthy, How does a Stochastic Approximation Algorithm Adapt to a Randomly Evolving Optimum with Jump Markov Sample Paths, Mathematical Programming B., (Special Issue dedicated to B.T. Polyak’s 70th Birthday), Vol.120, No.1, pp.67–99, 2009.
-
G. Yin and V. Krishnamurthy, Least Mean Squares Algorithms with Markov Regime Switching Limit, IEEE Transactions Automatic Control, Vol.50, No.5, pp.577–593, May 2005.
- G. Yin and V. Krishnamurthy, Analysis of LMS Algorithm for Slowly Varying Markovian Parameters – Tracking Slow Hidden Markov Models and Adaptive Multiuser Detection in DS/CDMA, IEEE Transactions Information Theory, Vol.51, No.7, pp.2475– 2490, July 2005
-
G. Yin, V. Krishnamurthy and C. Ion, Regime Switching Stochastic Approximation Algorithms with Application to Adaptive Discrete Stochastic Optimization, SIAM Journal on Optimization, Vol.14, No.4, pp.1187–1215, 2004.
-
V. Krishnamurthy and G. Yin, Recursive Algorithms for Estimation of Hidden Markov Models and Autoregressive Models with Markov Regime, IEEE Transactions on Information Theory, Vol.48, No.2, pp.458-476, Feb 2002.
- V. Krishnamurthy, X. Wang and G.Yin, Spreading Code Optimization and Adaptation in CDMA via Discrete Stochastic Approximation, IEEE Transactions on Information Theory, Vol.50, No.9, pp.1927–1949, Sept.2004.
Global Games, Bayesian Nash equilibria, Revealed Preferences
- W. Hoiles, V. Krishnamurthy, A. Aprem, PAC Algorithms for Detecting Nash Equilibrium Play in Social Networks: From Twitter to Energy Markets, IEEE Access Journal, Vol.4, Nov., pp.8147–8161, 2016.
- V. Krishnamurthy, Decentralized Activation in Sensor Networks Global Games and Adaptive Filtering Games, Digital Signal Processing, Vol.21, No.5, pp. 638{647, 2011.
- V. Krishnamurthy, Decentralized Spectrum Access amongst Cognitive Agents – An Interacting Multivariate Global Games Approach, IEEE Transactions Signal Processing, Vol.57, No.10, pp.3999-4013, Oct.2009.
- V. Krishnamurthy, Decentralized Activation in Dense Sensor Networks via Global Games, IEEE Transactions Signal Processing, Vol.56, No.10, pp.4936{4950, Oct.2008.