2022/01/28 by S. Rasoul Etesami, Etesami, S. Rasoul · 2 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Smart Grid Energy Management #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2201.12224
openalex publication_date 2022/01/28 · openalex created_date 2023/03/25 · openalex updated_date 2026/07/28
We consider a subclass of n-player stochastic games, in which players have their own internal state/action spaces while they are coupled through their payoff functions. It is assumed that players' internal chains are driven by independent transition probabilities. Moreover, players can receive only realizations of their payoffs, not the actual functions, and cannot observe each other's states/actions. For this class of games, we first show that finding a stationary Nash equilibrium (NE) policy without any assumption on the reward functions is interactable. However, for general reward functions, we develop polynomial-time learning algorithms based on dual averaging and dual mirror descent, which converge in terms of the averaged Nikaido-Isoda distance to the set of ε-NE policies almost surely or in expectation. In particular, under extra assumptions on the reward functions such as social concavity, we derive polynomial upper bounds on the number of iterates to achieve an ε-NE policy with high probability. Finally, we evaluate the effectiveness of the proposed algorithms in learning ε-NE policies using numerical experiments for energy management in smart grids.