Suggest edit — Factored MDPs

Title

Name

Note

---
title: "Factored MDPs"
type: concept
related: [Factored Mdps, Markov Decision Process]
source: https://www.jemoka.com/posts/kbhfactored_mdps/
confidence: high
status: active
---

Motivation Multiple agents need to collaborate to achieve common goal.
Joint Utility Maximization: maximize the joint utility between various agents.
Possible Approaches Using a traditional MDP: an MDP considers &ldquo;action&rdquo; as a joint action between all agents (exponential blow up because the agent actions multiply) Local Optimization: share rewards/values among agents Local Optimization: search and maximize joint utility explicitly (no need to model the entire action space) Problems with single Reward Sharing:
Credit Assignment Problem In collective reward situations, determining which action out of the cohort actually contributed to the award is hard.
Free Ride Problem Agents can benefit from reward without actually doing anything by being carried.
Factored MDPs Representation Using factored linear value function to approximate the joint value function Using linear programming to avoid exponential blow up Background Coordination Graphs modeling each agent as a node each edge is a dependency factored Markov Decision Process MDPs are not good at large problems factor the state and action spaces as a random variable factors, etc. action selection each agent maintains a local \(Q\) function indicating its population the \(Q\) function of each agent maybe influenced by other agents: the coordination graph of the agent is used to calculate contribution We optimize by using one agent at a time: we optimize one agent, then