Multiagent Rollout Algorithms and Reinforcement Learning

Understand

We consider finite and infinite horizon dynamic programming problems, where the control at each stage consists of several distinct decisions, each one made by one of several agents.

• We introduce an approach, whereby at every stage, each agent's decision is made by executing a local rollout algorithm that uses a base policy, together with some coordinating information from the other agents.
• The amount of local computation required at every stage by each agent is independent of the number of agents, while the amount of total computation (over all agents) grows linearly with the number of agents.
• By contrast, with the standard rollout algorithm, the amount of total computation grows exponentially with the number of agents.