Reinforcement learning with restrictions on the action set
This addresses the challenge of decentralized learning in game theory for scenarios with partial observability and constraints, though it is incremental as it builds on existing learning frameworks.
The paper tackles the problem of learning in repeated two-player games where players have limited information and restricted action sets, proving that empirical play distributions converge to Nash equilibria for zero-sum, potential, and two-action games.
Consider a 2-player normal-form game repeated over time. We introduce an adaptive learning procedure, where the players only observe their own realized payoff at each stage. We assume that agents do not know their own payoff function, and have no information on the other player. Furthermore, we assume that they have restrictions on their own action set such that, at each stage, their choice is limited to a subset of their action set. We prove that the empirical distributions of play converge to the set of Nash equilibria for zero-sum and potential games, and games where one player has two actions.