Tノート

いろいろ勉強したことをまとめていきます

MENU

Stochastic Games

Stochastic Games

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

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

$SG = <m,S,A,T,R>$

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

  • $ m $ はエージェント数

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

  • $A_i$ はエージェント $i$ が実行可能な行動の集合。 $ A = A_1 \times ... \times A_m $ はjoint action の集合。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} $$

  • $R_i$ : $S × A \mapsto R$ エージェント $i$ の報酬関数。この報酬も現在の状態 $s$ と joint action $A$によって決定

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

参考文献

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