Stochastic Games

Stochastic Gamesとは

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

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

$$
\begin{eqnarray}
SG = \langle n,S,A^1 ,...,A^n ,R^1 ,...,R^n ,T \rangle
\end{eqnarray}
$$

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

  • \(n\) :エージェント数
  • \(S\) :有限の状態の集合
  • \(A^1,...,A^n\) :エージェント群の行動の集合。 全エージェントの行動の組み合わせ(joint action)
  • \(T\) : 状態遷移関数 \(S \times A \times 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}
$$
  • \(R^1,...,R^n\) : エージェント群の報酬関数の集合。この報酬も現在の状態 \(s\) と joint action \(A\) によって決定。つまり \(S \times A \mapsto R\)

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

参考文献

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

コメント

タイトルとURLをコピーしました