Bayesian Delegation

Context

Wang2020 - Too Many Cooks: Coordinating Multi-agent Collaboration Through Inverse Planning uses Bayesian Delegation for decentralized cooking-style tasks. The mechanism infers which high-level subtask allocation other agents are pursuing, then chooses low-level actions that either complement the inferred allocation or participate in a joint subtask.

Formal Statement

Let ta range over high-level task allocations and let H_{0:T} be the public history of states and actions. The agent selects the most likely allocation

$$t{a}^{\ast }=\arg \underset{ta}{\max }P(ta\mid H_{0:T}),$$

with posterior

$$P(ta\mid H_{0:T})\propto P(ta)\prod _{t=0}^{T}P(a_t\mid s_t,ta).$$

The action likelihood is an inverse-planning softmax:

$$P(a_t\mid s_t,ta)\propto \exp (\beta Q_{ta}^{\ast }(s_t,a_t)).$$

Here beta controls how strongly observed actions are treated as approximately optimal for the hypothesized allocation.

Derivation / Construction

• Specify a partial order of subtasks for the task domain.
• Enumerate feasible allocations of agents to subtasks, including joint subtasks that require multiple agents.
• Maintain a prior P(ta) over allocations.
• Observe a public interaction history and update P(ta | H_{0:T}) using inverse-planning likelihoods.
• Choose the most likely allocation and pass its induced local goal to low-level planning.
• Use bounded real-time dynamic programming for low-level action selection and partner models for collision avoidance or joint role execution.

Implications

Bayesian Delegation makes coordination legible as belief update over latent plans. This is useful for ad hoc teamwork because it does not require explicit communication, but it inherits the assumptions of the inverse-planning model: if partner behavior is not well approximated by the hypothesized Q^*_{ta}, the posterior can become confidently wrong.

Links

• Wang2020 - Too Many Cooks: Coordinating Multi-agent Collaboration Through Inverse Planning
• Multi-Agent Coordination
• Ad Hoc Teamwork
• Cooperative Multi-Agent Reinforcement Learning