ノート

強化学習関連のこと

MENU

Stochastic Games

Stochastic Games

マルチエージェント強化学習を分析する際に有用な Stochastic Games(SG)について簡単にご紹介します。 ちなみにSGs は別名 Markov Gamesです。

SGは次のタプルで表現されます。

$ SG = < n,S,A1 ,...,An ,R1 ,...,Rn ,T> $

各要素については以下のようになります。

  • $n$ :エージェント数

  • $S$ :有限の状態の集合

  • $A1,...,An$ :エージェント群の行動の集合。 全エージェントの行動の組み合わせ(joint action)

  • $T$ : 状態遷移関数 $S × A × S \mapsto$ $[0; 1]$ 。状態 $s$ で全エージェントの行動(joint action) $A$ をとった時に $s_{t+1}$ に遷移する確率

$$ \begin{eqnarray} T(s, a, s^{'}) = P(s_{t+1} = s^{'} |a_t = a, s_t = s) \end{eqnarray} $$

  • $R1,...,Rn$ : エージェント群の報酬関数の集合。この報酬も現在の状態 $s$ と joint action $A$によって決定。つまり $S × A \mapsto R$

SGでは、すべてのエージェントが完全な状態 $s$ を観測できます。部分的にしか観測できない場合は別のフレームワークを用いる必要があります。(例えば Dec-POMDP等)。

参考文献

http://www.cs.cmu.edu/~mmv/papers/00TR-mike.pdf