Game-Theoretic Learning

We are interested in synthesizing and analyzing stochastic approximation algorithms for distributed optimization. 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. Our work is in collaboration with George Yin of Wayne State University, who is the expert in weak convergence analysis.

Related Papers

  1. O. Namvar, V.Krishnamurthy, G, Yin, Adaptive Search Algorithms for Discrete Stochastic Optimization: A Smooth Best-Response Approach, IEEE Trans Automatic Control, 2016.

  2. M. Hamdi, V. Krishnamurthy, G. Yin, Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph, IEEE Transactions Information Theory, 2014.

  3. O. Namvar, V. Krishnamurthy and G. Yin, Distributed Tracking of Correlated – Equilibria in Regime Switching Noncooperative Games, IEEE Transactions Automatic Control, pp.2435–2450, 2013.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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

  9. 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.

  10. 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.

  11. 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.

  12. 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.