部分モジュラーマルチエージェントポリシー学習によるオープンマルチエージェントシステムにおけるオンライン分散タスク割り当て

本論文は、submodularなチーム効用を持つmulti-agent reinforcement learning (MARL) におけるonline distributed task allocationを扱う。各agentはlocal categorical policyから1つのactionを選び、実行可能なjoint actionはagent-actionペア上のpartition matroidを成す。この設定で、Partition Multilinear Extension (PME) を導入し、SubMAPGというcentralized-training decentralized-execution (CTDE) のpolicy-gradient frameworkを提案する。open multi-agent systemsでの時変なagentとtargetに対応するため、graph neural network (GNN) policiesで実装する。

従来のmultilinear extensionはindependent Bernoulli samplingを用いるため、decentralized agentsが実行するcategorical policiesと一致しない。PMEはfactorized categorical policies下での期待チーム効用に一致する連続緩和であり、この不一致を解消する。また、submodular difference rewardsがPMEのmarginal-gradient情報を不偏に与えることを証明し、stagewise score-function policy-gradient estimatorを導出する。これにより、local greedyやshared-rewardベースラインを上回り、centralized myopic greedy戦略と競合する性能を示す。

PMEはpartition matroid上のcategorical policiesに対する連続緩和で、その値は期待チーム効用に等しい。submodular difference rewardsがPMEのmarginal-gradientを不偏に推定することを証明し、stagewise score-function policy-gradient estimatorを構成する。SubMAPGはmasked categorical policiesとsubmodular difference-reward training signalsを備えたCTDE policy-gradient framework。PME marginal-space projected stochastic-gradient dynamicsに対し、stagewise 1/2-approximation guaranteeと、最適PME marginalsのpath lengthで測るsublinear dynamic regretを証明。open systems向けにGNN policiesを採用。

multi-robot coverageとmulti-target trackingの実験で検証。SubMAPGはlocal greedyおよびshared-rewardベースラインを上回り、centralized myopic greedy戦略と競合する性能を示した。

PME marginal-space projected stochastic-gradient dynamicsに対して、stagewise 1/2-approximation guaranteeとsublinear dynamic regretを証明している。open systemsでの時変なagentとtargetへの対応としてGNN policiesを導入している。その他の限界や議論は要旨からは不明。

要旨で参照/比較されている研究として、classical multilinear extensions、local greedy、shared-reward baselines、centralized myopic greedy strategiesが挙げられる。関連手法としてsubmodular difference rewards、partition matroid、graph neural network policiesが挙げられる。