Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents

Decision-makers often adaptively influence downstream competitive agents’ behavior to minimize their cost, yet in doing so face critical challenges: $(i)$ decision-makers might not a priori know the agents’ objectives; $(ii)$ agents might learn their responses, introducing stochasticity and non-stationarity into the decision-making process; and $(iii)$ there may be additional non-strategic environmental stochasticity. Characterizing convergence of this complex system is contingent on how the decision-maker controls for the tradeoff between the induced drift and additional noise from the learning agent behavior and environmental stochasticity. To understand how the learning agents’ behavior is influenced by the decision-maker’s actions, we first consider a decision-maker that deploys an arbitrary sequence of actions which induces a sequence of games and corresponding equilibria. We characterize how the drift and noise in the agents’ stochastic algorithms decouples from their optimization error. Leveraging this decoupling and accompanying finite-time efficiency estimates, we design decision-maker algorithms that control the induced drift relative to the agent noise. This enables efficient finite-time tracking of game theoretic equilibrium concepts that adhere to the incentives of the players’ collective learning processes.